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

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

Инструкция . Введите выражение F(x) , нажмите Далее . Полученное решение сохраняется в файле Word . Также создается шаблон решения в Excel .

• Решение онлайн
• Видеоинструкция
• Оформление Word

Правила ввода функции, заданной в явном виде

2. Примеры правильного написания F(x) :
   1. 10•x•e 2x = 10*x*exp(2*x)
   2. x•e -x +cos(3x) = x*exp(-x)+cos(3*x)
   3. x 3 -x 2 +3 = x^3-x^2+3
   4. Выражение 0.9*x=sin(x)+1 необходимо преобразовать к виду: sin(x)+1-0.9*x . Аналогично, x^2-7=5-3x к виду x^2+3x-12 .

   Пусть дано уравнение f(x)=0 , где f(x) определено и непрерывно в некотором конечном или бесконечном интервале a ≤ x ≤ b . Всякое значение ξ, обращающее функцию f(x) в нуль, то есть такое, что f(ξ)=0 называется корнем уравнения или нулем функции f(x) . Число ξ называется корнем k -ой кратности, если при x = ξ вместе с функцией f(x) обращаются в нуль ее производные до (k-1) порядка включительно: f(ξ)=f’(ξ)= … =f k-1 (ξ) = 0 . Однократный корень называется простым.
   Приближенное нахождение корней уравнения складывается из двух этапов:

   1. Отделение корней, то есть установление интервалов [α_i,β_i] , в которых содержится один корень уравнения.
      1. f(a)•f(b) , т.е. значения функции на его концах имеют противоположные знаки.
      2. f’(x) сохраняет постоянный знак, т.е. функция монотонна (эти два условия достаточны, но НЕ необходимы) для единственности корня на искомом отрезке).
      3. f”(x) сохраняет постоянный знак, т.е. функция выпукла вверх, либо – вниз.
   2. Уточнение приближенных корней, то есть доведение их до заданной точности.

   Геометрическая интерпретация метода Ньютона (метод касательных)

   Критерий завершения итерационного процесса имеет вид

   Нелинейные системы и уравнения

   В более общем случае мы имеем не одно уравнение (1), а систему нелинейных уравнений $$ \begin \tag <2>f_i(x_1, x_2, \ldots, x_n) = 0, \quad i = 1, 2, \ldots n. \end $$ Обозначим через \( \mathbf = (x_1, x_2, \ldots, x_n) \) вектор неизвестных и определим вектор-функцию \( \mathbf(\mathbf) = (f_1(\mathbf), f_2(\mathbf), \ldots, f_n(\mathbf)) \). Тогда система (2) записывается в виде $$ \begin \tag <3>\mathbf(\mathbf) = 0. \end $$ Частным случаем (3) является уравнение (1) (\( n = 1 \)). Второй пример (3) — система линейных алгебраических уравнений, когда \( \mathbf (\mathbf) = A \mathbf — \mathbf \).

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

   Решение нелинейных уравнений

   При итерационном решении уравнений (1), (3) задается некоторое начальное приближение, достаточно близкое к искомому решению \( x^* \). В одношаговых итерационных методах новое приближение \( x_ \) определяется по предыдущему приближению \( x_k \). Говорят, что итерационный метод сходится с линейной скоростью, если \( x_ — x^* = O(x_k — x^*) \) и итерационный метод имеет квадратичную сходимость, если \( x_ — x^* = O(x_k — x^*)^2 \).

   В итерационном методе Ньютона (методе касательных) для нового приближения имеем $$ \begin \tag <4>x_ = x_k + \frac, \quad k = 0, 1, \ldots, \end $$

   Вычисления по (4) проводятся до тех пор, пока \( f(x_k) \) не станет близким к нулю. Более точно, до тех пор, пока \( |f_(x_k)| > \varepsilon \), где \( \varepsilon \) — малая величина.

   Простейшая реализация метода Ньютона может выглядеть следующим образом:

   Чтобы найти корень уравнения \( x^2 = 9 \) необходимо реализовать функции

   Данная функция хорошо работает для приведенного примера. Однако, в общем случае могут возникать некоторые ошибки, которые нужно отлавливать. Например: пусть нужно решить уравнение \( \tanh(x) = 0 \), точное решение которого \( x = 0 \). Если \( |x_0| \leq 1.08 \), то метод сходится за шесть итераций.

   Теперь зададим \( x_0 \) близким к \( 1.09 \). Возникнет переполнение

   Возникнет деление на ноль, так как для \( x_7 = -126055892892.66042 \) значение \( \tanh(x_7) \) при машинном округлении равно \( 1.0 \) и поэтому \( f^\prime(x_7) = 1 — \tanh(x_7)^2 \) становится равной нулю в знаменателе.

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

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

   Учитывая выше сказанное реализуем функцию с учетом следующего:

   1. обрабатывать деление на ноль
   2. задавать максимальное число итераций в случае расходимости метода
   3. убрать лишний вызов функции f(x)

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

   При реализации метода Ньютона нужно знать аналитическое выражение для производной \( f^\prime(x) \). Python содержит пакет SymPy, который можно использовать для создания функции dfdx . Для нашей задачи это можно реализовать следующим образом:

   Решение нелинейных систем

   Идея метода Ньютона для приближенного решения системы (2) заключается в следующем: имея некоторое приближение \( \pmb^ <(k)>\), мы находим следующее приближение \( \pmb^ <(k+1)>\), аппроксимируя \( \pmb(\pmb^<(k+1)>) \) линейным оператором и решая систему линейных алгебраических уравнений. Аппроксимируем нелинейную задачу \( \pmb(\pmb^<(k+1)>) = 0 \) линейной $$ \begin \tag <5>\pmb(\pmb^<(k)>) + \pmb(\pmb^<(k)>)(\pmb^ <(k+1)>— \pmb^<(k)>) = 0, \end $$ где \( \pmb(\pmb^<(k)>) \) — матрица Якоби (якобиан): $$ \pmb<\nabla F>(\pmb^<(k)>) = \begin \frac<\partial f_1(\pmb^<(k)>)> <\partial x_1>& \frac<\partial f_1(\pmb^<(k)>)> <\partial x_2>& \ldots & \frac<\partial f_1(\pmb^<(k)>)> <\partial x_n>\\ \frac<\partial f_2(\pmb^<(k)>)> <\partial x_1>& \frac<\partial f_2(\pmb^<(k)>)> <\partial x_2>& \ldots & \frac<\partial f_2(\pmb^<(k)>)> <\partial x_n>\\ \vdots & \vdots & \ldots & \vdots \\ \frac<\partial f_n(\pmb^<(k)>)> <\partial x_1>& \frac<\partial f_n(\pmb^<(k)>)> <\partial x_2>& \ldots & \frac<\partial f_n(\pmb^<(k)>)> <\partial x_n>\\ \end $$ Уравнение (5) является линейной системой с матрицей коэффициентов \( \pmb \) и вектором правой части \( -\pmb(\pmb^<(k)>) \). Систему можно переписать в виде $$ \pmb(\pmb^<(k)>)\pmb <\delta>= — \pmb(\pmb^<(k)>), $$ где \( \pmb <\delta>= \pmb^ <(k+1)>— \pmb^ <(k)>\).

   Таким образом, \( k \)-я итерация метода Ньютона состоит из двух стадий:

   1. Решается система линейных уравнений (СЛАУ) \( \pmb(\pmb^<(k)>)\pmb <\delta>= -\pmb(\pmb^<(k)>) \) относительно \( \pmb <\delta>\).

   2. Находится значение вектора на следующей итерации \( \pmb^ <(k+1)>= \pmb^ <(k)>+ \pmb <\delta>\).

   Для решения СЛАУ можно использовать приближенные методы. Можно также использовать метод Гаусса. Пакет numpy содержит модуль linalg , основанный на известной библиотеке LAPACK, в которой реализованы методы линейной алгебры. Инструкция x = numpy.linalg.solve(A, b) решает систему \( Ax = b \) методом Гаусса, реализованным в библиотеке LAPACK.

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

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

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

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

   

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

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

   

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

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

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

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

   

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

   ,

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

   

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

   

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

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

   

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

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

   

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

   

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

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

   

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

   

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

   

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

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

   

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

   

   — значение первой частной производной функции F_j по переменной x_i при значении переменных

   

   

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

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

   

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

   

   

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

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

   

   Итерационная процедура далее продолжается аналогично.

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

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

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

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

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

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

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

   Для функции F ₁ 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 помещены начальные приближения к решению системы (значения х ₀ и у ₀ , соответственно). В диапазоне ячеек D3:E4 помещены формулы для вычисления матрицы Якоби, при условии что х находится в ячейке В3, а у — в ячейке В4 (формулы приведены на рисунке ниже). В ячейках G3:G4 рассчитывается значение вектора невязок с отрицательным знаком.

   

   В ячейке Н3 вычисляется эвклидова норма вектора невязок. В ячейках I3:I4 — решается система линейных уравнений и вычисляется вектор поправок к решению. Для этого обращается матрица коэффициентов системы (матрица Якоби) и умножается на вектор-столбец свободных членов (отрицательный вектор невязок). Формула в этот диапазон ячеек вводится как формула массива. Рядом — в ячейке J3 — рассчитывается норма вектора поправок для контроля сходимости (см. формулы на рисунке ниже).

   

   Полученные в ячейках I3:I4 значения поправок на втором итерационном цикле прибавляются к начальному приближению (в ячейках В6:В7) и далее вычисления повторяются аналогично первому циклу.

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

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

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

   Если аппроксимирующую функцию и определяющие ее параметры a_i обозначить следующим образом

   

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

   

   Другой пример — поиск экстремума (минимума или максимума) функции нескольких переменных

   

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

   
   

   источники:

   http://slemeshevsky.github.io/num-mmf/snes/html/._snes-FlatUI001.html

   http://physchem.chimfak.sfedu.ru/Source/NumMethods/Sys_non-lin_eq.html