Численные методы (стр. 3 )

Чтобы было возможным решение систем большого числа уравнений, необходимо изменить метод вычислений и сделать его менее трудоемким.

Известный из курсов элементарной и высшей математики метод Гаусса[7] (или метод Жордана[8]) сводит посредством эквивалентных преобразований, исходную систему линейных уравнений к системе с верхней треугольной матрицей. Число операций, требуемое при этом для решения системы n уравнений, имеет порядок . При больших n эта величина во много раз меньше, чем . Так, для n = 20 она имеет значение 3270, и поэтому система двадцати уравнений по методу Гаусса может быть решена на ЭВМ.

С точки зрения высшей математики система линейных уравнений всегда является или вырожденной (не имеющей решения, или имеющей бесконечно много решений), или невырожденной (решение существует и единственно). С точки же зрения практических вычислений могут существовать почти вырожденные системы, при решении которых получаются недостоверные значения неизвестных.

Рассмотрим систему исходных уравнений:

Эта система имеет единственное решение . Рассмотрим пару значений неизвестных . При подстановке этих значений в рассматриваемые уравнения получаем

После округления до двух значащих цифр правые части полученных равенств совпадают с правыми частями исходной системы уравнений. Если коэффициенты исходных уравнений заданы только с точностью до двух значащих цифр, то решение так же хорошо отвечает условиям поставленной задачи, как и решение .

Дело в том, что две прямые линии, описываемые двумя уравнениями исходной системы, почти параллельны. Точка хотя и не лежит ни на одной из этих прямых линий, но очень близка к ним. Системы, подобные рассмотренной, называются плохо обусловленными. В любом случае, когда две линии (либо плоскости и гиперплоскости) почти параллельны, система уравнений становится плохо обусловленной. В этом случае найти численное решение системы трудно, а точность его сомнительна. Более того, система из трех и более уравнений может оказаться плохо обусловленной, даже если никакие плоскости не являются параллельными или почти параллельными[9]. Причиной плохой обусловленности является малая величина определителя системы уравнений.

2.2. Основные понятия

Методы решения систем линейных уравнений обычно разделяют на две большие группы.

К первой группе относят методы, которые принято называть точными: они позволяют для любых систем найти точные значения неизвестных после конечного числа арифметических операций, каждая из которых выполняется точно (без округлений). Примерами таких методов являются метод Крамера, метод исключения неизвестных Гаусса, метод Жордана.

Ко второй группе относят методы, не являющиеся точными. Их называют приближенными. Приближенные методы даже в том случае, когда вычисления ведутся без округлений, позволяют получить решение лишь приближенно с заданной точностью. Основным представителем этой группы методов являются итерационные[10] методы.

Итерационные методы дают возможность найти решение системы как предел бесконечного вычислительного процесса, позволяющего по уже найденным приближениям к решению построить следующее, более точное приближение. Достоинством этих методов является их самоисправляемость (самонастраиваемость) и простота. Если в точных методах ошибка в вычислениях, когда она не компенсируется случайно другими ошибками, неизбежно ведет к ошибкам в результате, то в случае сходящегося итерационного процесса ошибка в каком-то приближении исправляется в последующих вычислениях, и такое исправление требует, как правило, только нескольких лишних шагов единообразных вычислений.

Схематически процесс получения решения системы n линейных уравнений итерационным методом можно изобразить следующим образом. Задается начальное (нулевое) приближение , затем в результате выполнения первой итерации, получается первое приближенное решение , в результате выполнения -й итерации получается -ое приближенное решение и т. д. Итерационный процесс называется сходящимся, если последовательность приближенных решений сходится к точному решению , т. е. если существует каждый из указанных ниже пределов и

Условия и скорость сходимости каждого итерационного метода существенно зависят от свойств системы линейных уравнений и от выбора начальных приближений.

2.3. Информация, которая должна быть известна пользователю

итерационным методом

·  Достаточное условие сходимости.

·  Итерационные формулы, которые позволяют получить последующее значение, зная предыдущее.

·  Что нужно брать за нулевое (начальное) приближение.

·  Когда остановить (прервать) бесконечный процесс получения приближенных решений и при этом быть уверенным, что окончательное приближение будет получено с заданной точностью.

·  Как оценить погрешность приближенного решения.

·  Итерационных методов построено большое число. Остановимся только на двух основных – методе простой итерации и методе Гаусса–Зейделя.

2.4. Метод простой итерации (метод Якоби[11])

Пусть система линейных уравнений имеет вид:

1.  Достаточным условием сходимости метода простой итерации является диагональное преобладание, которое имеет вид для всех .

Это условие означает, что в каждом уравнении системы модуль диагонально коэффициента должен быть больше суммы модулей всех остальных коэффициентов этого уравнения.

2.  Итерационные формулы могут быть получены следующим образом. Если система приведена к виду с диагональным преобладанием, то для получения итерационных формул нужно каждое уравнение системы разрешить относительно диагонального неизвестного, т. е.:

(2.1)

3.  можно взять любой набор чисел, и несмотря на это диагональное преобладание обеспечит сходимость к точному решению.

От того насколько удачно выбрано нулевое приближение зависит скорость сходимости, т. е. количество итераций, обеспечивающее заданную точность.

Если имеется какая-нибудь информация о решении, то при выборе нулевого приближения надо ей воспользоваться. Если такой информации нет, то можно, например, задать:

.

4.  Оценка погрешности приближенного решения, получаемого методом простой итерации дается следующим неравенством:

,

где – точное значение -го неизвестного,

– значение -го неизвестного, полученное на -й итерации,

– некоторый коэффициент. Чтобы определить нужно:

a)  раскрыть скобки в правой части всех уравнений системы (2.1);

b)  вычислить сумму модулей коэффициентов при неизвестных в каждом уравнении в правой части;

c)  в качестве взять наибольшую из этих сумм.

5.  Обычно в условии задачи оговаривается точность с которой необходимо найти решение. Эта точность задается в виде положительного числа и означает следующее: как только для всех выполнится условие , то решение с заданной точностью будет найдено. Значит итерационный процесс на –й итерации можно закончить и в качестве приближенного решения системы взять числа ,,…,.

Пользоваться неравенством неудобно, т. к. точное решение неизвестно (если бы оно было известно, то тогда незачем искать приближенное).

Поэтому на практике пользуются другим условием для окончания итерационного процесса. Получим это условие. Из неравенства в силу следует выполнение неравенства . Следовательно, как только выполнится условие , итерационный процесс можно будет закончить, т. к. приближенное решение будет вычислено с заданной точностью.

2.5. Метод Гаусса–Зейделя

Метод Гаусса-Зейделя обладает большей скоростью сходимости по сравнению с методом простой итерации. Он отличается от метода простой итерации только итерационными формулами, которые при вычислении значения на –й итерации используют уже найденные значения ,,…, на этой же итерации:

Тема 3. Численные методы решения нелинейных уравнений

с одной переменной

3.1. Основные понятия

3.1.1. Уравнение и его корни

При решении практических задач приходится сталкиваться с решением уравнений. Всякое уравнение с одной переменой можно представить в виде , где и — данные функции, определенные на некотором числовом множестве , называемом областью допустимых значений уравнения.

Уравнение с одной переменной можно записать в виде .

Действительно, перенеся в левую часть , имеем уравнение , равносильное исходному. Если обозначить левую часть последнего уравнения через , то получим уравнение .

Совокупность значений независимой переменной , при которых уравнение превращается в тождество, называется решением этого уравнения, а каждое значение из этой совокупности называется корнем уравнения (или корнем функции ).

Решить уравнение — значит найти множество всех корней этого уравнения. Оно может быть конечным или бесконечным. Так, например уравнение имеет решение . Придавая различные значения, получаем бесконечное множество корней.

Корни уравнения могут быть действительными и комплексными. В дальнейшем будет идти речь только о вычислении действительных корней.

В зависимости от того, какие функции входят в уравнение , уравнения можно разделить на два больших класса: алгебраические и трансцендентные[12].

Функция называется алгебраической, если для получения значения функции по данному значению нужно выполнить арифметические операции (сложение, вычитание, умножение, деление) и возведение в степень с рациональным показателем. (Операция извлечения корня может быть представлена как операция возведения в степень с показателем 1/n).

Функция называется трансцендентной, если она не является алгебраической. К неалгебраическим функциям относятся: показательная , логарифмическая , тригонометрические , , , , обратные тригонометрические и другие.

Если в запись уравнения входят только алгебраические функции, то оно называется алгебраическим.

Алгебраическое уравнение может быть приведено к виду:

.

Поэтому, когда говорят «алгебраическое уравнение», то обычно имеют в виду именно уравнение этого вида. Показатель называется степенью уравнения, числа называются коэффициентами уравнения, они могут быть как действительными, так и комплексными. В дальнейшем будем рассматривать алгебраические уравнения только с действительными коэффициентами.

Уравнения делятся на:

а) линейные: ,

б) нелинейные.

Нелинейность проявляется, например, в том, что независимая переменная входит в уравнение под знаком степени , где , или под знаком трансцендентной функции.

Примеры нелинейных уравнений:

При решении любого уравнения необходимо:

1) установить имеет ли оно действительные корни;

2)вычислить любой из действительных корней или точно (если это возможно и имеет смысл), или приближенно с заданной степенью точности . Последнее означает следующее.

Пусть — корень уравнения, причем и . Тогда числа и могут рассматриваться как приближенные значения корня соответственно с недостатком и с избытком с точностью до , так как

и .

Заметим, что любое число, содержащееся между и , можно принять за приближенное значение корня с точностью до .

При решении многих практических задач точное решение уравнения не всегда является необходимым. Задача нахождения корней считается решенной, если корни вычислены с заданной степенью точности.

Принято выделять прямые и приближенные методы решения нелинейных уравнений.

3.1.2. Прямые методы решения нелинейных уравнений

Прямым называется метод, который позволяет найти решение уравнения с помощью формулы и обеспечивает получение точного решения. Примером прямого метода является нахождение корней алгебраического уравнения второй степени. Известны также формулы Кардана для нахождения корней уравнений 3-й и формулы Феррари для нахождения корней уравнений 4-й степени. Эти формулы содержат радикалы 2-й и 3-й степени, сложны и мало пригодны для практики. Поэтому приближенные методы применяются и для решения уравнений 3-й и 4-й степени. Однако уже алгебраические уравнения 5-й степени и выше в общем случае в радикалах разрешены быть не могут, т. е. не удается построить формулу для отыскания корней их корней (см. пункт 3.3).

Кроме того, коэффициенты некоторых уравнений являются приближенными числами и, следовательно, вопрос о нахождении точных корней вообще не может быть поставлен.

В некоторых случаях решение трансцендентных уравнений сводится к алгебраическим уравнениям, вообще же трансцендентные уравнения могут быть решены только приближенно.

3.1.3. Приближенные методы решения нелинейных уравнений

Иногда приближенное значение корня бывает известно из экономических или физических соображений, в других случаях можно использовать графические и численные методы.

Г р а ф и ч е с к и й м е т о д. Пусть дано уравнение . Постоим график функции . Абсциссы точек пересечения графика с осью OX и являются корнями уравнения.

Иногда для графического решения уравнения удобнее записать его в виде и построить графики функций: и . Абсциссы точек пересечения этих графиков и будут корнями уравнения .

П р и м е р 3.1. Решить графически уравнение . Представим данное уравнение в виде . Строим графики функций и . Абсциссы точек пересечения графиков дают корни уравнения . Видим, что эти абсциссы лежат в интервалах ,,.

П р и м е р 3.2. Решить графически уравнение . Представим данное уравнение в виде . Строим графики функций и ( — радианная мера угла). Принимая во внимание свойства функций и , убеждаемся, что в интервале данное уравнение имеет единственный корень .

Однако графический метод позволяет получить лишь грубо приближенные значения корней уравнения. Для получения значений корней с большей точностью применяются численные методы. Тем не менее, графический метод очень удобен, так как он позволяет найти корни с точностью, достаточной для решения некоторых практических задач, а также достаточно нагляден, прост и поэтому доступен.

Ч и с л е н н ы е м е т о д ы р е ш е н и я у р а в н е н и й. Процесс нахождения приближенных значений корней разбивается на два этапа:

1.  Отделение корней.

2.  Уточнение корней до заданной степени точности.

Отделение корней. Корень уравнения отделен на отрезке , если он содержится в данном отрезке, и если на этом отрезке других корней нет.

Провести полное отделение всех корней уравнения — значит разбить всю область допустимых значений на интервалы (или на отрезки), в каждом из которых содержится ровно по одному корню (или не содержится ни одного корня).

Отделение корней обычно начинают проводить графически. Для этого строят графики функций, получают интервалы, в которых находятся корни уравнения. Это предположение затем проверяют аналитически, пользуясь свойствами непрерывных и дифференцируемых функций, которые изучаются в курсе математического анализа. Приведем основные теоремы, знание которых полезно для решения вопросов этого рода.

Т е о р е м а 1. (Теорема о существовании корня) Если функция непрерывна на отрезке и принимает на концах этого отрезка значения разных знаков, т. е. , то внутри отрезка существует по крайней мере один корень уравнения .

Заметим, что при выполнении условий теоремы 3.1 корней может оказаться несколько.

Т е о р е м а 2. (Теорема о существовании и единственности корня) Если функция непрерывна и монотонна на отрезке и принимает на концах этого отрезка значения разных знаков, т. е. , то внутри отрезка содержится корень уравнения и этот корень единственный.

Т е о р е м а 3. (Теорема о существовании и единственности корня) Если функция непрерывна на отрезке и принимает на концах этого отрезка значения разных знаков, т. е. , а производная сохраняет постоянный знак внутри отрезка, то внутри отрезка существует корень уравнения , и притом единственный.

Заметим, что утверждения теорем 2. и 3. является лишь достаточными условиями изоляции корня. Теорема 3. чаще применяется для строгого решения задачи об отделении корней.

П р и м е р 3.3. Вернемся к уравнению . Вычислим производную функции : . Очевидно, что при , следовательно, при и имеем . Соответственно при – .

Поскольку

то и интервал является интервалом изоляции корня.

Поскольку

,

то и интервал является интервалом изоляции корня.

Поскольку

,

то и интервал является интервалом изоляции корня.

П р и м е р 3.4. Дано уравнение . Докажем что существует единственный корень уравнения, заключенный между числами и . Функция непрерывна на отрезке , принимает на концах этого отрезка значения и , которые имеют разные знаки. Кроме того, на всем отрезке . Следовательно, в силу теоремы 3.3, на отрезке имеется корень уравнения, и притом единственный. Поэтому исследуемый отрезок является интервалом изоляции корня.

Необходимо обратить внимание, что все предлагаемые ниже методы приближенного решения уравнения ориентированы на поиск единственного корня. В случае если на исследуемом интервале изменения аргумента (от точки до точки ) уравнение имеет два или несколько корней необходимо разбить интервал на более мелкие отрезки для поиска единственного решения на каждом из них. При наличии нескольких корней на интервале некоторые из предлагаемых методов применять просто нельзя – нарушается условие сходимости итераций. Но даже устойчивый метод, такой как дихотомия, даст в результате вычислений лишь один корень, остальные будут потеряны.

3.2. Численные методы решения нелинейных уравнений

3.2.1. Метод деления отрезка пополам

Метод деления отрезка пополам (иначе называемый дихотомией[13]) – один из простейших и довольно наглядный метод решения нелинейных уравнений. Заключается он в следующем. Предположим, что функция обращается в нуль в интервале числовой оси и единожды меняет знак. То есть . На саму функцию накладывается лишь требование непрерывности. (Мы убедимся в дальнейшем, что большинство методов накладывает более жесткие требования на функцию ).

В ходе итераций каждый раз делим область поиска корня уравнения пополам, вычисляем в середине отрезка значение функции и, в зависимости от ее знака, выбираем зоной поиска правую, либо левую половину отрезка, так, чтобы на концах нового (вдвое меньшего уже) отрезка функция по-прежнему принимала разные знаки.

В результате такого многократного деления отрезка , правая и левая его границы стягиваются к точке – корню уравнения . Уменьшение вдвое интервала поиска на каждой новой итерации определяет скорость сходимости вычислительного процесса. Запишем размер интервала после -й итерации деления .

Отсюда очевидная оценка погрешности , где