Главная > Экологическое > Решение систем нелинейных уравнений. Системы нелинейных уравнений Метод простой итерации пример решения уравнения


Решение систем нелинейных уравнений. Системы нелинейных уравнений Метод простой итерации пример решения уравнения




Все люди от природы стремятся к знанию. (Аристотель. Метафизика)

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

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

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

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

Итак, возникает целый класс задач, связанных с нахождением решений нелинейных уравнений, например, уравнения или уравнения и т.д.

В простейшем случае у нас имеется функция , заданная на отрезке (a , b ) и принимающая определенные значения.

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

Нам нужно найти такое значение при котором такие называются корнями функции

Визуально нам нужно определить точку пересечения графика функции с осью абсцисс.

Метод деления пополам

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

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

Алгоритм состоит в следующем.

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

Поделим отрезок пополам и введем среднюю точку .

Тогда либо , либо .

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

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

Заметьте, описанный алгоритм применим для любой непрерывной функции.

К достоинствам метода деления пополам следует отнести его высокую надежность и простоту.

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

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

Метод Ньютона: теоретические основы

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

Уравнение касательной к функции в точке имеет вид:

В уравнении касательной положим и .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

Таким образом, сходимость метода касательных Ньютона очень быстрая.

Запомните этот замечательный факт!

Без всяких изменений метод обобщается на комплексный случай.

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

Упражнение 1 . Найти с помощью метода касательных решение уравнения на отрезке (0, 2).

Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3).

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

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

Визуализация метода Ньютона

Метод Ньютона (метод касательных) применяется в том случае, если уравнение f (x ) = 0 имеет корень , и выполняются условия:

1) функция y = f (x ) определена и непрерывна при ;

2) f (a )· f (b ) < 0 (функция принимает значения разных знаков на концах отрезка [a ; b ]);

3) производные f" (x ) и f"" (x ) сохраняют знак на отрезке [a ; b ] (т.е. функция f (x ) либо возрастает, либо убывает на отрезке [a ; b ], сохраняя при этом направление выпуклости);

Основная идея метода заключается в следующем: на отрезке [a ; b ] выбирается такое число x 0 , при котором f (x 0 ) имеет тот же знак, что и f "" (x 0 ), т. е. выполняется условие f (x 0 )· f "" (x ) > 0 . Таким образом, выбирается точка с абсциссой x 0 , в которой касательная к кривой y = f (x ) на отрезке [a ; b ] пересекает ось Ox . За точку x 0 сначала удобно выбирать один из концов отрезка.

Рассмотрим метод Ньютона на конкретном примере.

Пусть нам дана возрастающая функция y = f(x) =x 2 -2, непрерывная на отрезке (0;2), и имеющая f " (x) = 2 x > 0 и f "" (x) = 2 > 0 .

Рисунок 1 . f(x) =x 2 -2

Уравнение касательной в общем виде имеет представление:

y-y 0 = f " (x 0)·(x-x 0).

В нашем случае: y-y 0 =2x 0 ·(x-x 0). В качестве точки x 0 выбираем точку B 1 (b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B 1 , и обозначаем точку пересечения касательной и оси Ox точкой x 1 . Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6.

Ox: x 1 =

Рисунок 2. Результат первой итерации

y=f(x) Ox через точку x 1 , получаем точку В 2 =(1.5; 0.25) . Снова проводим касательную к функции y = f(x) в точке В 2 , и обозначаем точку пересечения касательной и оси Ox точкой x 2 .

Уравнение второй касательной: y -0.25=2*1.5(x -1.5), y = 3 x - 4.25.

Точка пересечения касательной и оси Ox: x 2 = .

Рисунок 3. Вторая итерация метода Ньютона

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x 2 , получаем точку В 3 и так далее.

Рисунок 4. Третий шаг метода касательных

Первое приближение корня определяется по формуле:

= 1.5.

Второе приближение корня определяется по формуле:

=

Третье приближение корня определяется по формуле:

Таким образом, i -ое приближение корня определяется по формуле:

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e - до выполнения неравенства | xi - xi -1 | < e .

В нашем случае, сравним приближение, полученное на третьем шаге с реальным ответом, посчитанном на калькуляторе:

Рисунок 5. Корень из 2, посчитанный на калькуляторе

Как видно, уже на третьем шаге мы получили погрешность меньше 0.000002.

Таким образом можно вычислить значение величины "корень квадратный из 2" с любой степенью точности. Этот замечательный метод был изобретен Ньютоном и позволяет находить корни очень сложных уравнений.

Метод Ньютона: приложение на С++

В данной статье мы автоматизируем процесс вычисления корней уравнений, написав консольное приложение на языке C++. Разрабатывать его мы будем в Visual C++ 2010 Express, это бесплатная и очень удобная среда разработки С++.

Для начала запустим Visual C++ 2010 Express. Появится стартовое окно программы. В левом углу нажмем «Создать проект».

Рис. 1. Начальная страница Visual C++ 2010 Express

В появившемся меню выберем «Консольное приложение Win32», введем имя приложение «Метод_Ньютона».

Рис. 2. Создание проекта

// Метод_Ньютона.cpp: определяет точку входа для консольного приложения

#include "stdafx.h"

#include

using namespace std;

float f(double x) //возвращает значение функции f(x) = x^2-2

float df(float x) //возвращает значение производной

float d2f(float x) // значение второй производной

int _tmain(int argc, _TCHAR* argv)

int exit = 0, i=0;//переменные для выхода и цикла

double x0,xn;// вычисляемые приближения для корня

double a, b, eps;// границы отрезка и необходимая точность

cout<<"Please input \n=>";

cin>>a>>b; // вводим границы отрезка, на котором будем искать корень

cout<<"\nPlease input epsilon\n=>";

cin>>eps; // вводим нужную точность вычислений

if (a > b) // если пользователь перепутал границы отрезка, меняем их местами

if (f(a)*f(b)>0) // если знаки функции на краях отрезка одинаковые, то здесь нет корня

cout<<"\nError! No roots in this interval\n";

if (f(a)*d2f(a)>0) x0 = a; // для выбора начальной точки проверяем f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // считаем первое приближение

cout<<++i<<"-th iteration = "<

while(fabs(x0-xn) > eps) // пока не достигнем необходимой точности, будет продолжать вычислять

xn = x0-f(x0)/df(x0); // непосредственно формула Ньютона

cout<<++i<<"-th iteration = "<

cout<<"\nRoot = "<

cout<<"\nExit?=>";

} while (exit!=1); // пока пользователь не ввел exit = 1

Посмотрим, как это работает. Нажмем на зеленый треугольник в верхнем левом углу экрана, или же клавишу F5.

Если происходит ошибка компиляции «Ошибка error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден», то это лечится либо установкой первого Service pack 1, либо в настройках проекта Свойства -> Компоновщик отключаем инкрементную компоновку.

Рис. 4. Решение ошибки компиляции проекта

Мы будем искать корни у функции f(x) = x2-2 .

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

У нас появилось окно приложения:

Рис. 5. Ввод входных данных

Введем границы отрезка 3 и 5, и точность 0.05. Программа, как и надо, выдала сообщение об ошибке, что на данном отрезке корней нет.

Рис. 6. Ошибка «На этом отрезке корней нет!»

Выходить мы пока не собираемся, так что на сообщение «Exit?» вводим «0».

Теперь проверим работу приложения на корректных входных данных. Введем отрезок и точность 0.0001.

Рис. 7. Вычисление корня с необходимой точностью

Как мы видим, необходимая точность была достигнута уже на 4-ой итерации.

Чтобы выйти из приложения, введем «Exit?» => 1.

Метод секущих

Чтобы избежать вычисления производной, метод Ньютона можно упростить, заменив производную на приближенное значение, вычисленное по двум предыдущим точкам:

Итерационный процесс имеет вид:

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

Порядок сходимости метода секущих ниже, чем у метода касательных и равен в случае однократного корня .

Эта замечательная величина называется золотым сечением:

Убедимся в этом, считая для удобства, что .

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

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

После подстановки имеем: и

Для сходимости необходимо, чтобы было положительным, поэтому .

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

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

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

Такая процедура определения момента окончания итераций называется приемом Гарвика.

Метод парабол

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

Для этого заменим, аналогично методу секущих, функцию интерполяционной параболой проходящей через точки , и .

В форме Ньютона она имеет вид:

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

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

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

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

Метод простых итераций

Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки.

Пусть и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что).

По теореме Банаха существует и единственна неподвижная точка

Она может быть найдена как предел простой итерационной процедуры

где начальное приближение — произвольная точка промежутка .

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

Таким образом, если производная меньше единицы, то является сжатием.

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

Задание:

1) Используя метод итераций, решить систему

2) Используя метод Ньютона, решить систему

нелинейных уравнений с точностью до 0,001.

Задание №1Используя метод итераций, решить систему нелинейных уравнений с точностью до 0,001.

Теоретическая часть.

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

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

Метод Ньютона , алгоритм Ньютона (также известный как метод касательных) - это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643-1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства. Обоснование

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

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

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:

С учётом этого функция определяется выражением:

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

.

Варианты заданий

№1. 1)
2)

№2. 1)
2)

№3. 1)
2)

№4. 1)
2)

№5. 1)
2)

№6. 1)
2)

№7. 1)
2)

№8. 1)
2)

№9. 1)
2)

№10.1)
2)

№11.1)
2)

№12.1)
2)

№13.1)
2)

№14.1)
2)

№15.1)
2)

№16.1)
2)

№17.1)
2)

№18.1)
2)

№19.1)
2)

№20.1)
2)

№21. 1)
2)

№22. 1)
2)

№23. 1)
2)

№24. 1)
2)

№25. 1)
2)

№26. 1)
2)

№27. 1)
2)

№28. 1)
2)

№29. 1)
2)

№30. 1)
2)

Образец выполнения задания

№1. 1)
2)

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



Перепишем данную систему в виде:

Отделение корней производим графически (рис.1). Из графика видим, что система имеет одно решение, заключенное в области D: 0<х <0,3;-2,2<y <-1,8.

Убедимся в том, что метод итераций применим для уто­чнения решения системы, для чего запишем ее в следующем виде:

Так как ,то имеем в области D

+ = ;

+ =

Таким образом, условия сходимости выполняются.

Таблица №2

п
0,15 -2 -0,45 -0,4350 -0,4161 -0,1384
0,1616 -2,035 -0,4384 -0,4245 -0,4477 -0,1492
0,1508 -2.0245 -0,4492 -0,4342 -0,4382 -0,1461
0.1539 -2,0342. -0,4461 -0.4313 -0,4470 -0,1490
0.1510 -2,0313 -0,4490 -0,4341 -0,4444 -0.1481
0,1519 -2,0341 -0,4481 -0,4333 -0,4469 -0,1490
0,1510 -2.0333 -0.449 -0,4341 -0.4462 -0,1487
0.1513 -2.0341 -0,4487 -0,4340 -0,4469 -0.1490
0.1510 -2,0340

За начальные приближения принимаем х о =0,15, у 0 = -2.

(таб.№2). Тогда ответ запишется:

Пример решения системы нелинейных уравнений методом Ньютона

Отделение корней производим графически (рис.2). Для построения графиков функций составим таблицу значений функций и , входящих в первое и второе уравнения (табл. I).

Значения для x можно брать исходя из следующих условий: из первого уравнения 1≤1,2х+0,4≤1 , т.е. 1,16≤х≤0,5 ; из второго уравнения , т.е. . Таким образом, .

Система имеет два решения. Уточним одно из них, принадлежащее области D: 0,4<x <0,5;

0,76<y <0,73. За начальное приближение примем Имеем:


Таблица №3

x -1,1 -1 -0,8 -0,6 -0,2 -0,4 0,2 0,4 0,5
х 2 1.21 0,64 0,36 0,04 0,16 0,04 0.16 0,25
0,8 х 2 0,97 0,8 0,51 0,29 0,032 0,13 0,032 0,13 0,2
1 -0,8 х 2 0,03 0,2 0,49 0,71 0,97 0,87 0,97 0.87 0,8
0,02 0,13 0,33 0,47 0,65 0,58 0,67 0,65 0,58 0.53
±0,14 ±0,36 ±0,57 ±0,69 ±0,81 ±0,76 ±0,82 ±0.81 ±0,76 ±0.73
1,2x -1,32 -1,2 -0,9б" -0,72 -0,24 -0,48 0,24 0,48 0,6
0,4+1,2x -0,92 -0,8 -0,56 -0,32 0,16 -0,08 0,4 0,64 0.88
2x-y -1.17 -0,93 -0,59 -0,33 0,16 -0,08 0,41 0,69 2.06 1,08 1,57
-1,03 -1,07 -1,01 -0,87 -0,56 -0,72 -0,41 -0,29 -1,26 -1,28 -0.57

Уточнение корней проводим методом Ньютона:



где ; ;


;
;


Все вычисления производим по таблице 3

Таблица 3 0,10 0,017 -0,0060 0,0247 -0,0027 -0,0256 0,0001 0,0004
0,2701 0,0440 -0,0193 0,0794 -0,0080 -0,0764 -0,0003 0,0013
2,6197 3,2199 2,9827 3,1673
-0,0208 -2,25 0,1615 -2,199 0,1251 -2,1249 0,1452 -2,2017
-1,1584 0,64 -1,523 0,8 -1,4502 0,7904 -1,4904 0,7861
0,1198 -0,0282 -0,0131 0,059 -0,0007 -0,0523 -0,0002 0,0010
0,9988 0,0208 0,9869 -0,1615 0,9921 -0,1251 -0,9894 -0,1452
0,55 0,733 1,6963 1,7165
0,128 0,8438 0,2 0,8059 0,1952 0,7525 0,1931 0,8079
0,4 0,75 0,50 -0,733 0,4940 -0,7083 0,4913 -0,7339 0,4912 -0,7335 Ответ: x ≈0,491 y ≈ 0,734
n

Контрольные вопросы

1) Представьте на графике возможные случаи решения системы двух нелинейных уравнений.

2) Сформулируйте постановку задачи о решении системы n-линейных уравнений.

3) Приведите итерационные формулы метода простой итерации в случае системы двух нелинейных уравнений.

4) Сформулируйте теорему о локальной сходимости метода Ньютона.

5) Перечислите трудности, возникающие при использовании метода Ньютона на практике.

6) Объяснить каким образом можно модифицировать метод Ньютона.

7) Изобразите в виде блок-схем алгоритм решения систем двух нелинейных уравнений методами простой итерации и Ньютона.


Лабораторная работа №3

ЛАБОРАТОРНАЯ РАБОТА №3-4.

Вариант №5.

Цель работы: научиться решать системы нелинейных уравнений (СНУ) методом простых итераций (МПИ) и методом Ньютона с помощью ЭВМ.

1. Изучить МПИ и метод Ньютона для решения систем нелинейных уравнений.

2. На конкретном примере усвоить порядок решения систем нелинейных уравнений МПИ и методом Ньютона с помощью ЭВМ.

3. Составить программу и с ее помощью решить систему уравнений с точностью .

ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ

Задание.

1. Аналитически решить СНУ:

2. Построить рабочие формулы МПИ и метода Ньютона для численного решения системы при начальном приближении: .

3. Составить программу на любом языке программирования, реализующую построенный итерационный процесс.

Решение.

Аналитический метод.

Аналитическим решением СНУ являются точки и .

Метод простых итераций (МПИ).

Для построения рабочих формул МПИ для численного решения системы необходимо вначале привести ее к виду:

Для этого умножим первое уравнение системы на неизвестную постоянную , второе - на , затем сложим их и добавим в обе части уравнения . Получим первое уравнение преобразуемой системы:

Неизвестные постоянные определим из достаточных условий сходимости итерационного процесса:

Запишем эти условия более подробно:

Полагая равными нулю выражения под знаком модуля, получим систему линейных алгебраических уравнений (СЛАУ) 4 порядка с 4 неизвестными :

Для решения системы необходимо вычислить частные производные :

Тогда СЛАУ запишется так:

Заметим, что если частные производные мало изменяются в окрестности начального приближения, то:

Тогда СЛАУ запишется так:

Решением этой системы являются точки , , , . Тогда рабочие формулы МПИ для решения СНУ примут вид:

Для реализации на ЭВМ рабочие формулы можно переписать так:

Итерационный процесс можно начать, задав начальное приближение x 0 =-2, y 0 =-4. Процесс заканчивается при одновременном выполнении двух условий: и . В этом случае значения и являются приближенным значением одного из решений СНУ.

Метод Ньютона.

Для построения рабочих формул метода Ньютона в виде


где , необходимо:

1. Найти матрицу частных производных:

2. Найти определитель этой матрицы:

3. Определить обратную матрицу:

Проведя преобразования:

Получаем рабочую формулу метода Ньютона для реализации на ЭВМ:

Блок-схема МПИ и метода Ньютона для решения СНУ приведена на рисунке 1.

Рис.1 Схемы МПИ и метода Ньютона.

Тексты программ:

Program P3_4; {Iterations}

uses Crt;

var n: integer;

clrscr;

xn:=x-(x-y+2)+(1/2)*(x*y-3);

yn:=y+(2/3)*(x-y+2)+(1/6)*(x*y-3);

writeln (n:3, x:9:5, xn:9:5, (xn-x):9:5, y:9:5, yn:9:5, (yn-y):9:5);

n:=n+1;

until (abs(x-zx)<=eps) and (abs(y-zy)<=eps);

readln;

2) Метод Ньютона:

Program P3_4; {Nyuton}

uses Crt;

var n: integer;

x0,x,xn,y0,y,yn,eps,zx,zy:real;

clrscr;

n:=0; x0:=-2; x:=x0; y0:=-4; y:=y0; eps:=0.001;

writeln (" n x(i) x(i+1) x(i+1)-x(i) y(i) y(i+1) y(i+1)-y(i) ");

xn:=x-(1/(x+y))*(x*x-x*y+2*x+x-y+2);

yn:=y-(1/(x+y))*(x*y*(-y)-3*(-y)+x*y-3);

writeln (n:3, x:9:5, xn:9:5, abs(xn-x):9:5, y:9:5, yn:9:5, abs(yn-y):9:5);

n:=n+1;

until (abs(x-zx)<=eps) and (abs(y-zy)<=eps);

Результаты отработки программы:

· Рис.2 – программы, работающей по методу простых итераций;

· Рис.3 – программы, работающей по методу Ньютона.

Рис.2 Ответ: х(16)≈-3.00023, у(16)≈-1.00001

Рис.3 Ответ: х(8)≈-3.00000, у(8)≈-1.00000

Кафедра физхимии ЮФУ (РГУ)
ЧИСЛЕННЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ
Материалы к лекционному курсу
Лектор – ст. преп. Щербаков И.Н.

Системы нелинейных уравнений

При решении задач моделирования поведения химических систем достаточно часто приходится решать системы уравнений, нелинейных по отношению к переменным. Системы n линейных уравнений с n неизвестными x 1 , x 2 , ..., x n в общем случае принято записывать следующим образом:

где F 1 , F 2 ,…, F n – любые функции независимых переменных, в том числе и нелинейные относительно неизвестных.

Как и в случае систем линейных уравнений, решением системы является такой вектор (или векторы) (X * ) , который при подстановке обращает одновременно все уравнения системы в тождества.

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

Рассмотрим несколько простейших итерационных методов решения систем нелинейных уравнений, а именно, метод простой итерации, метод Зейделя и метод Ньютона.

Метод простой итерации

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

Выбирая затем вектор начального приближения

подставляют его в преобразованную систему уравнений. Из первого уравнения получают новое приближение к первой переменной, из второго – второй и т. д. Полученное уточненное значение переменных снова подставляют в эти уравнения и т.д.Таким образом, на (i+1 ) -м шаге итерационной процедуры имеем

Метод Зейделя

Модификация Зейделя алгоритма простой итерации заключается в использовании уточненных значений переменных уже на текущем итерационном шаге. Так, для уточнения значений первой переменной используются только значения предыдущего шага, для второй переменной – значение x 1 текущего шага, а остальных – от предыдущего и т.д.:

Метод Ньютона-Рафсона

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

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

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

Вспомним, что для функции одной переменной разложение в ряд Тейлора в окрестности некоторой точки x 0 имеет следующий вид:

после пренебрежения всеми членами, кроме линейного:

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

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

Запишем для функции F 1 2-х переменных линейную часть разложения в ряд Тейлора в окрестности выбранной точки

для второго уравнения, аналогично

Если значения переменных x 1 и x 2 являются решением, то оба уравнения системы должны обратиться в ноль, поэтому полученные разложения приравниваем нулю.

Для краткости записи введем следующие обозначения:

Приращение i -ой переменной

Значение первой частной производной функции F j по переменной x i при значении переменных

– значение j -ой функции при соответствующих значениях переменных, то есть невязка j ‑го уравнения.

Получим систему линейных уравнений 2 x 2 относительно приращения переменных

Или, в матричной форме,

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

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

Таким образом, процедура решения выглядит следующим образом:

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

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

3. Решается система линейных уравнений относительно приращений переменных.

4. к вектору начального приближения прибавляется вектор приращений

5. проверяется условие сходимости и, если оно не достигнуто, то процедура повторяется с п. 2.

Метод легко обобщается на систему уравнений любой размерности.

Для функции F 1 n переменных линейная часть разложения в ряд Тейлора в окрестности точки записывается так

После разложения всех уравнений системы и используя введенные ранее обозначения, после преобразования получим систему линейных уравнений порядка n относительно приращения переменных Δ x i

Или, в матричной форме,

В сокращенном виде можно записать так - (F" )(Δ x ) = - (F ) , где матрица значений частных производных – (F" ) – называется матрицей Якоби или якобианом системы уравнений.

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

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

где эпсилон – достаточно малое число.

Методы контроля сходимости итерационных методов
решения систем

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

1. Норма (эвклидова или -максимум) вектора невязок

2. Эвклидова норма вектора относительных отклонений переменных

3. Норма-максимум вектора относительных отклонений

Применим метод Ньютона для решения системы уравнений

Матрица частных производных (в аналитическом виде)

Система линейных уравнений

Может быть решена аналитически или методом Крамера или методом обращения матрицы. Возьмем начальное приближение x = 0,15, y = 0,17

Первая итерация:

Матрица Якоби - вектор значений функции Рассчитанный вектор поправок Новое приближение x = 0,15 + 0,028704 = 0,178704, y = 0,17 + 0,090926 = 0,260926 Вторая итерация: Рассчитанный вектор поправок Новое приближение x = 0,196656, y = 0,293359 Третья итерация: Рассчитанный вектор поправок Новое приближение x = 0,199867, y = 0,299739 Уже на 6-й итерации эвклидова норма вектора невязок составляет 2.8∙10 -13 , максимальное относительное изменение переменных составляет 1.6∙10 -12 и решение сходится к x = 0.2, y = 0.3 с абсолютной погрешностью менее 5∙10 -7 . Метод простой итерации при этих же начальных условиях сходится с такой точностью на 33-м шаге, модификация Зейделя – на 31-м шаге. На рисунке ниже представлен пример организации вычислений при решении рассмотренной системы в программе MS Excel
Пояснения: В ячейки В3 и В4 помещены начальные приближения к решению системы (значения х 0 и у 0 , соответственно). В диапазоне ячеек D3:E4 помещены формулы для вычисления матрицы Якоби, при условии что х находится в ячейке В3, а у - в ячейке В4 (формулы приведены на рисунке ниже). В ячейках G3:G4 рассчитывается значение вектора невязок с отрицательным знаком.
В ячейке Н3 вычисляется эвклидова норма вектора невязок. В ячейках I3:I4 - решается система линейных уравнений и вычисляется вектор поправок к решению. Для этого обращается матрица коэффициентов системы (матрица Якоби) и умножается на вектор-столбец свободных членов (отрицательный вектор невязок). Формула в этот диапазон ячеек вводится как формула массива . Рядом - в ячейке J3 - рассчитывается норма вектора поправок для контроля сходимости (см. формулы на рисунке ниже).
Полученные в ячейках I3:I4 значения поправок на втором итерационном цикле прибавляются к начальному приближению (в ячейках В6:В7) и далее вычисления повторяются аналогично первому циклу. Набранные в строках 6 и 7 рабочего листа формулы могут копироваться до тех пор, пока не будет достигнута необходимая точность.

Задачи, сводящиеся к решению системы нелинейных уравнений

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

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

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

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

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

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

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

1.1. Постановка задачи

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

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

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

Геометрически корень уравнения есть точка пересечения графика функции с осью абсцисс. На рис. 1 изображен график функции , имеющей четыре корня: два простых и два кратных .


Большинство методов решения уравнения ориентировано на отыскание простых корней.

1.2. Основные этапы отыскания решения

В процессе приближенного отыскания корней уравнения обычно выделяют два этапа: локализация (или отделение) корня и уточнение корня .

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

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

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

1.3. Метод половинного деления

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

Разделим отрезок пополам. Получим точку . Вычислим значение функции в этой точке: . Если , то - искомый корень, и задача решена. Если , то - число определённого знака: либо . Тогда либо на концах отрезка , либо на концах отрезка значения функции имеют разные знаки. Обозначим такой отрезок . Очевидно, что и длина отрезка в два раза меньше, чем длина отрезка . Поступим аналогично с отрезком . В результате получим либо корень , либо новый отрезок и т. д. (рис. 2).

Середина -го отрезка . Очевидно, что длина отрезка будет равна , а так как , то

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

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

Следовательно, не позднее 6-го деления найдем с требуемой точностью, . Результаты вычислений представлены в таблице 1.

Таблица 1

1,0000 1,0000 1,0000 1,1250 1,1250 1,1406 1,1406
2,0000 1,5000 1,2500 1,2500 1,1875 1,1875 1,1562
1,5000 1,2500 1,1250 1,1875 1,1406 1,1562 1,1484
Зн - - - - - - -
Зн + + + + + + +
5,5938 0,7585 -0,2959 0,1812 -0,0691 0,0532 -0,0078
- 1,0000 0,5000 0,2500 0,1250 0,0625 0,0312 0,0156

1.4. Метод простой итерации

Пусть уравнение можно заменить эквивалентным ему уравнением

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

Формула (3) является расчетной формулой метода простой итерации.

Если последовательность сходится при , т. е. существует

и функция непрерывна, то, переходя к пределу в (3) и учитывая (4), получим: .

Таким образом, , следовательно, - корень уравнения (2).

Сходимость метода. Сходимость метода простой итерации устанавливает следующая теорема.

Теорема. Пусть функция определена и диффе-ренцируема на отрезке , причем все ее зна-чения . Тогда, если выполняется условие при :

1) процесс итерации сходится независимо от начального значения ;

2) предельное значение является единственным корнем уравнения на отрезке .

Доказательство. Так как и , то можно записать

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

Если ввести обозначение для всего интервала поиска, то предыдущее равенство может быть переписано в виде:

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

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

или и тогда .

Вывод неравенства.Рассмотрим два последовательных приближения: и . Отсюда .

Используя теорему о среднем, получим:

тогда на основании условия можно записать:

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

Тогда или .

Используя предыдущую формулу, можно получить:

Перейдём к пределу в равенстве (3), в силу непрерывности функции получим , то есть - корень уравнения (2). Других корней на нет, так как если , то , тогда , где . Равенство нулю будет достигнуто, если . То есть - корень единственный.

Теорема доказана.

Приведение уравнения к виду
для обеспечения выполнения неравенства

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

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

Обычно принимают .

На рис. 3-6 показаны четыре случая взаимного расположения линий и и соответствующие итерационные процессы. Рис. 3 и 4 соответствуют случаю , и итерационный процесс сходится. При этом, если (рис. 3), сходимость носит односторонний характер, а если (рис. 4), сходимость носит двусторонний, колебательный характер. Рис. 5 и 6 соответствуют случаю - итерационный процесс расходится. При этом может быть односторонняя (рис. 5) и двусторонняя (рис. 6) расходимость.

Погрешность метода. Оценка погрешности была доказана (5).

Критерий окончания. Из оценки (5) следует, что вычисления надо продолжать до выполнения неравенство . Если же , то оценка упрощается: .

Пример 1. Используем метод простой итерации для решения уравнения с точностью . Преобразуем уравнение к виду:

, т. е. .

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

поэтому внутри отрезка есть корень. Расположение корня наглядно иллюстрирует рис. 7.

Подсчитаем первую и вторую производные функции :

Так как на отрезке , то производная монотонно возрастает на этом отрезке и принимает максимальное значение на правом конце отрезка, т. е. в точке . Поэтому справедлива оценка:

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

Таблица 2

0,8415 0,8861 0,8712 0,8774 0,8765

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

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

0,8 0,78

Так как , то .

1.5. Метод Ньютона (метод касательных)

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

Уравнение касательной будет иметь вид: .

Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью , т. е. положив : .

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

Формула (6) является расчетной формулой метода Ньютона .

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

Сходимость метода . Сходимость метода Ньютона устанавливает следующая теорема.

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

Сходимость метода Ньютона зависит от того, насколько близко к корню выбрано начальное приближение.

Выбор начального приближения. Пусть - отрезок, содержащий корень. Если в качестве начального приближения выбрать тот из концов отрезка, для которого , то итерации (6) сходятся, причем монотонно. Рис. 8 соответствует случаю, когда в качестве начального приближения был выбран правый конец отрезка: (Здесь ).

Погрешность метода. Оценка (7) неудобна для практического использования. На практике пользуются следующие оценки погрешности:

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

Пример . Вычислить методом Ньютона отрицательный корень уравнения с точностью до 0,0001. Проведя отделение корня, можно убедиться, что корень локализован на интервале . В этом интервале и . Так как и , то за начальное приближение можно принять .

-11 -5183 0,6662
-10,3336 307,3 4276,8 0,0718
-10,2618 3,496 4185,9 0,0008
-10,261 0,1477 - -

. Поэтому . Итак, в результате получаем следующее, и на , поэтому .

Так как , то