Упрощенный метод Ньютона

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

 

Тема: Метод Ньютона

 

Руководитель Рогов В.П.

Исполнитель студент гр. С-110 Щелков Е.И.

 

 

Работу выполнил:

Работу защитил:

 

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

 

Вывод итерационной формулы

Рис. 1.3

 

 

 

из последнего соотношения получаем

Алгоритм метода Ньютона:

1) принимаем и вводим в ЭВМ начальное значение x и допустимую погрешность вычисления корня ε;

2) присваиваем величине x ₀ значение x;

3) вычисляем новое значение

;

4) анализируем условие . если это условие выполняется, то переходим к пункту 2, т. е. продолжаем поиск корня; иначе выводим в качестве результата величину x.

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

.

Такой подход иллюстрируется на рис. 1.4.

 

а б

 

Рис. 1.4: а – начало; б – продолжение

Алгоритм метода Ньютона с разностной производной:

1) вводим в ЭВМ x и ε;

2) формируем дополнительную точку x ₁ = x + 0,1;

3) формируем две точки для проведения секущей

x ₀ = x ₁,

x ₁ = x;

4) вычисляем новое значение

;

5) анализируем условие . если это условие выполняется, то переходим к пункту 3, т. е. продолжаем поиск корня; иначе выводим в качестве результата величину x.

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

Упрощенный метод Ньютона

 

Если производная функции f ′(x) в процессе поиска корня изменяется мало, то можно еë вычислить один раз в начальной точке x ₀.

Тогда итерационная формула поиска запишется в виде:

Данный подход иллюстрируется на рис. 1.5.

 

 

Рис. 1.5

Метод Ньютона сходится быстро, однако для обеспечения его сходимости нужно определённым образом задавать начальную точку x ₀.

Условие сходимости (необходимое и достаточное) (см. рис. 1.6):

.

 

 

а б

 

Рис. 1.6

 

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

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

 

 

Дана система нелинейных уравнений с n неизвестными:

(1.14)

Разложим в ряд Тейлора каждую функцию f_i (x ₁, x ₂,…, x_n) в начальной точке , обозначив ,

(1.15)

где α(p ²) – бесконечно малое по сравнению с

Учитывая в разложении (1.15) только линейные члены относительно и заметив, что из (1.14) имеем f_i (x ₁, x ₂,…, x_n) = 0, получаем систему линейных уравнений относительно приращений :

В развёрнутой матричной форме полученная система уравнений будет иметь следующий вид:

 

(1.16)

Введя векторные обозначения, можем записать систему (1.16) в виде

JD_x = – F,

где J – квадратная матрица Якоби;

D_x – вектор приращений Δ x_j;

F – вектор правых частей системы.

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

Алгоритм решения:

1) ввод исходных данных:

ε – допустимая абсолютная погрешность в вычислении решения;

n – количество уравнений для вычисления неизвестных x_j;

m – максимальное количество итераций;

X ₀ – вектор начальных приближений

h – приращение x_j для вычисления частных производных в разностной форме;

2) вычисление элементов вектора F в начальной (текущей) точке, определяемой вектором X ₀;

3) вычисление элементов матрицы J – частных производных:

4) решение линейной системы (1.16) – вычисление элементов вектора D_x;

5) корректировка начального (текущего) приближения решения – вычисление вектора

6) проверка погрешности решения по условию

При выполнении этого условия вектор X выводится в качестве решения системы, а иначе переформируется вектор начальных приближений (X ₀ = X) и осуществляется переход к пункту 2 на выполнение очередной итерации. Количество итераций ограничивается числом m. При его превышении выдается сообщение о необходимости выбора лучшего начального приближения.

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

Каждой из нелинейных функций и , стоящих в левой части первого и второго уравнений, соответствует в пространстве некоторая изогнутая поверхность y ₁ и y ₂. В точке начального приближения будем иметь значения функций:

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

Эти выражения описывают касательные плоскости к поверхностям y ₁ и y ₂ в соответствующих точках с координатами . Эти плоскости имеют следы пересечения с плоскостью x ₁ Ox ₂ в виде прямых линий. В свою очередь пересечение этих прямых даёт точку очередного приближения к решению системы (рис. 1.7).

 

 

Практическая часть: