Metodichka_po_kursovoy_rabote

21

Приложение 1

Пример возможного выполнения раздела «Анализ, формальная постановка и

выбор метода решения»

( http://physics.herzen.spb.ru/library/01/01/nm_labs/nonlineareq.htm )

ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

1.Понятия и определения

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

В общем случае нелинейное уравнение с одним неизвестным можно записать в виде:

называется корнем уравнения (2.1). Если в точке x x* наряду с функцией обращаются в ноль и

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

В зависимости от вида функции f (x) нелинейные уравнения подразделяются на два класса – алгебраические и трансцендентные1[1].

Уравнение (2.1) называется алгебраическим, если функция f (x) является алгебраической функцией. Алгебраическое уравнение всегда может быть представлено в канонической форме:

где a0 , a1, , an – коэффициенты уравнения. Показатель n называют степенью алгебраического уравнения.

трансцендентным. Примерами трансцендентных уравнений являются:

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

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

.

+

на отрезке [ A, B]. Выбор этого отрезка (интервала поиска корней) может быть сделан, например, на основе анализа конкретной физической или иной задачи. Будем вычислять

значения f (x) , начиная с точки x1 A , двигаясь вправо с некоторым шагом h (рис. 2.3). Как

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

Надежность рассмотренного подхода к отделению корней уравнений зависит как от характера функции f (x) , так и от выбранной величины шага h. Действительно, если при достаточно малом значении h ( h | B A |) на границах текущего отрезка [x; x h] функция

f (x) принимает значения одного знака, то естественно ожидать, что уравнение f (x) 0 корней на этом отрезке не имеет. Однако, это не всегда так: при несоблюдении условия

монотонности функции f (x) на отрезке [x; x h] могут оказаться корни уравнения (рис. 2.4а).

Также несколько корней на отрезке [x; x h]

f (x) f (x h) 0 (рис. 2.4б). Предвидя подобные ситуации, следует выбирать достаточно малые значения h.

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

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

численных экспериментов с варьированием параметров задачи, когда приходится многократно

24

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

3. Уточнение корней. На данном этапе задача состоит в получении приближенного значения корня, принадлежащего отрезку [a,b], с заданной точностью (погрешностью) . Это

Процедура численного определения приближенных значений корней нелинейных уравнений, как правило, состоит в выборе начального приближения к корню x0 [a,b] и

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

приближенных значений корня x0 , x1, ,xk , , которая называется итерационной последовательностью. Если эти значения с ростом k стремятся к точному значению корня x :

то говорят, что итерационный процесс сходится.

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

где q 0 и 1 – некоторые числа, значения которых определяются методом уточнения корня. От значений q и зависит насколько с каждым шагом уменьшается погрешность приближенных значений и, соответственно, насколько быстро можно получить приближенное значение с заданной точностью. Главным показателем скорости сходимости метода является

значение , называемое порядком сходимости. При 1 погрешность с каждым шагом

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

§ 2. Методы уточнения корней

1. Метод половинного деления (бисекции, дихотомии)

25

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

приближения корня принимаем середину этого отрезка: c0 (a b) / 2 (рис. 2.5). Затем

После каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после k

итераций в 2k раз:

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполнено условие (2.9).

26

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

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

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

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

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

и прекратить итерационный процесс при попадании в нее. Если принять f , то

Также необходимо иметь ввиду, что при уменьшении интервала [a,b] увеличиваются погрешности вычисления его длины b a за счет вычитания близких чисел. 3[3]

2. Метод хорд

Рассматриваемый метод так же, как и метод половинного деления, предназначен для уточнения корня на интервале [a,b], на концах которого функция f (x) принимает значения

27

разных знаков. Очередное приближение в отличие от метода половинного деления берем не в

середине отрезка, а в точке x0 , где пересекает ось абсцисс прямая линия (хорда), проведенная через точки А и В (рис. 2.6).

Запишем уравнение прямой, проходящей через точки А и В:

Для рассматриваемого случая (рис. 2.6) выбираем отрезок [a, x0 ], так как f (a) f (x0 ) 0 .

или при выполнении условия (2.12).

 З а м е ч а н и е . Метод половинного деления и метод хорд очень похожи, в частности, процедурой проверки знаков функции на концах отрезка. При этом второй их них в ряде случаев дает более быструю сходимость итерационного процесса. Однако в некоторых случаях метод хорд может сходится существенно медленнее метода половинного деления. Такая ситуация показана на рис. 2.7. Оба рассмотренных метода не требуют знания дополнительной информации

28

Аналогично могут быть найдены и следующие приближения. Формула для k+1-го приближения имеет вид

дифференцируемой и f (x) в окрестности корня не должна менять знак.

Для окончания итерационного процесса могут быть использованы условия (2.12) или (2.14).

 З а м е ч а н и е 1 . В методе Ньютона, в отличие от предыдущих методов, не обязательно задавать отрезок [a,b], содержащий корень уравнения, а достаточно найти некоторое начальное приближение корня x0 .

 З а м е ч а н и е 2 . Формула метода Ньютона может быть получена и из других соображений. Зададимся некоторым начальным приближением корня x0 [a,b] . Заменим функцию f(x) в окрестности точки x0 отрезком ряда Тейлора:

f (x) f (x0 ) (x x0 ) f (x0 ) ,

и вместо нелинейного уравнения f (x) 0 решим линеаризованное уравнение

f (x0 ) (x x0 ) f (x0 ) 0

рассматривая его решение как следующее (первое) приближение к искомому значению корня. Решение этого уравнение очевидно: