Численные методы алгебры

Размещено на http://allbest.ru

Министерство образования и науки РФ

Ульяновский государственный университет

Инженерно-физический факультет высоких технологий

РЕФЕРАТ

Численные методы алгебры

Направление: 21.03.01«Нефтегазовое дело»

Выполнил

студент группы НДМ-В-21/1

С.Н. Ваштахов

Доцент, к.т.н. Е.А. Цынаева

Ульяновск 2021



Содержание

Введение

1. Метод Гаусса

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

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

4. Метод релаксации

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

6. Метод наискорейшего спуска



Введение

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

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



1. Метод Гаусса

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

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

Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления.

Прямой ход состоит из n? 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x₁ из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a₁₁? 0. Будем называть его главным элементом 1-го шага.

Найдем величины

q_i1 = a_i1/a₁₁ (i = 2, 3, …, n),

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q₂₁, q₃₁, …, q_n1. Это позволит обратить в нуль коэффициенты при x₁ во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n= b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n= b₂⁽¹⁾ ,

a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + … + a_3n⁽¹⁾x_n= b₃⁽¹⁾ ,

. . . . . . . . . . . . . . .

a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + … + a_nn⁽¹⁾x_n= b_n⁽¹⁾ .

в которой a_ij⁽¹⁾ и b_ij⁽¹⁾ вычисляются по формулам

a_ij⁽¹⁾ = a_ij ? q_i1a_1j , b_i⁽¹⁾ = b_i ? q_i1b₁.

2-й шаг. Целью этого шага является ислючение неизвестного x₂ из уравнений с номерами i = 3, 4, …, n. Пусть a₂₂⁽¹⁾ ? 0, где a₂₂⁽¹⁾- коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

q_i2 = a_i2⁽¹⁾ / a₂₂⁽¹⁾ (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q₃₂, q₄₂, …, q_m2. В результате получим систему

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n= b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾ = b₂⁽¹⁾ ,

a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

. . . . . . . . . . . . . . . . . . .

a_n3⁽²⁾x₃ + … + a_nn⁽²⁾x_n= b_n⁽²⁾ .

Здесь коэффициенты a_ij⁽²⁾ и b_ij⁽²⁾ вычисляются по формулам

a_ij⁽²⁾ = a_ij⁽¹⁾ - q_i2a_2j⁽¹⁾ , b_i⁽²⁾ = b_i⁽¹⁾ - q_i2b₂⁽¹⁾.

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k-й шаг. В предположении, что главный (ведущий) элемент k-го шага a_kk^(k-¹⁾ отличен от нуля, вычислим множители k-го шага

q_ik = a_ik^(k-¹⁾ / a_kk^(k-¹⁾ (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на q_k+1,k, q_k+2,k, …, q_nk.

После (n - 1)-го шага исключения получим систему уравнений

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

. . . . . . . . . . . . . . . . . . . .

a_nn⁽ⁿ-¹⁾x_n = b_n⁽ⁿ-¹⁾ .

матрица A^(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение x_n в предпоследнее уравнение, получим x_n-₁. Осуществляя обратную подстановку, далее последовательно находим x_n-₁, x_n-₂, …, x₁. Вычисления неизвестных здесь проводятся по формулам

x_n = b_n⁽ⁿ-¹⁾ / a_nn⁽ⁿ-¹⁾,

x_k = (b_n^(k-¹⁾ - a_k,k+1^(k-¹⁾x_k+1 - … - a_kn^(k-¹⁾x_n) / a_kk^(k-¹⁾, (k = n - 1, …, 1).

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы a_kk^(k-¹⁾. Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

a_ij^(k) = a_ij^(k-¹⁾? q_ika_kj , b_i^(k) = b_i^(k-¹⁾ ? q_ikb_k^(k-¹⁾, i = k + 1, …, n.

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

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |q_ik| ? 1 для всех k = 1, 2, …, n - 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk^(k-1). После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления.

Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора)

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

На 1-м шаге мтода среди элементов a_ij определяют максимальный по модулю элемент a_i1j1. Первое уравнение системы и уравнение с номером i₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_i1 из всех уравнений, кроме первого.

На k-м шаге метода среди коэффициентов a_ij^(k-¹⁾ при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент a_ikjk^(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное x_jk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: x_jn, x_jn-1, …, x_j1.



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

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

Методы решения нелинейных уравнений делятся на две группы:

1. точные методы;

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

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

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

Пусть дано уравнение

	(1)

где:

1. Функция f(x) непрерывна на отрезке [a, b] вместе со своими производными 1-го и 2-го порядка.

2. Значения f(x) на концах отрезка имеют разные знаки (f(a) ? f(b) < 0).

3. Первая и вторая производные f' (x) и f'' (x) сохраняют определенный знак на всем отрезке.

Условия 1) и 2) гарантируют, что на интервале [a, b] находится хотя бы один корень, а из 3) следует, что f(x) на данном интервале монотонна и поэтому корень будет единственным.

Решить уравнение (1) итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.

Всякое значение , обращающее функцию f(x) в нуль, т.е. такое, что:

называется корнемуравнения (1) или нулем функции f(x).

Задача нахождения корня уравнения f(x) = 0 итерационным методом состоит из двух этапов:

1. отделение корней - отыскание приближенного значения корня или содержащего его отрезка;

2. уточнение приближенных корней - доведение их до заданной степени точности.

Процесс отделения корней начинается с установления знаков функции f(x) в граничных x = a и x = b точках области ее существования.

Пример 1. Отделить корни уравнения:

f(x)є x3 - 6х + 2 = 0.	(2)

Составим приблизительную схему:

x	-?	-3	-1	0	1	3	+?
f(x)	-	-	+	+	-	+	+

Следовательно, уравнение (2) имеет три действительных корня, лежащих в интервалах [-3, -1], [0, 1] и [1, 3].

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

В инженерной практике распространен графический способ определения приближенных корней.

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

,	(3)

где функции f₁(x) и f₂(x) - более простые, чем функция f(x). Тогда, построив графики функций у = f₁(x) и у = f₂(x), искомые корни получим как абсциссы точек пересечения этих графиков.

Рисунок 2.

Пример 2.Графически отделить корни уравнения (Рисунок 2):

x lg x = 1.	(4)

Уравнение (4) удобно переписать в виде равенства:

lg x=.

Отсюда ясно, что корни уравнения (4) могут быть найдены как абсциссы точек пересечения логарифмической кривой y = lg x и гиперболы y = . Построив эти кривые, приближенно найдем единственный корень уравнения (4) или определим его содержащий отрезок [2, 3].

Итерационный процесс состоит в последовательном уточнении начального приближения х₀. Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня х₁, х₂, ..., х_n. Если эти значения с увеличением числа итераций n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится.

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

Для использования метода итерации исходное нелинейное уравнение f(х) = 0 заменяется равносильным уравнением

x = j(x).	(8)

Пусть известно начальное приближение корня х = х₀. Подставляя это значение в правую часть уравнения (8), получим новое приближение:

х1 = j(х0).

Далее, подставляя каждый раз новое значение корня в (8), получаем последовательность значений:

	(9)

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

Рисунок 6.

Отправляясь от некоторой точки А₀[x₀,j(x₀)], строим ломаную А₀В₁А₁В₂А₂... (“лестница”), звенья которой попеременно параллельны оси Ох и оси Оу, вершины А₀, А₁, А₂, ...лежат на кривой у=j(х), а вершины В₁, В₂, В₃, …, - на прямой у = х. Общие абсциссы точек А₁ и В₁, А₂ и В₂, ..., очевидно, представляют собой соответственно последовательные приближения х₁, х₂, ... корня .

Возможен также другой вид ломаной А₀В₁А₁В₂А₂ ... - “спираль” (Рисунок 6, б). Решение в виде “лестницы” получается, если производная j' (х) положительна, а решение в виде “спирали”, если j' (х) отрицательна.

На Рисунке 6, а, б кривая у = j (х) в окрестности корня - пологая, то есть <1, и процесс итерации сходится. Однако, если рассмотреть случай, где >1, то процесс итерации может быть расходящимся (Рисунок 7).

Рисунок 7.

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

Теорема: Пусть функция? (х) определена и дифференцируема на отрезке [a, b], причем все ее значения? (х) [a, b].

Тогда, если существует правильная дробьqтакая, что

q < 1

при a < x < b,то: 1) процесс итерации

сходится независимо от начального значения х_{0 ?}[a, b];

2) предельное значениеявляется единственным корнем уравнениях = j(х) на отрезке [a, b].

Пример 5. Уравнение

f(x) =--x3 - x- 1 = 0	(10)

имеет корень x--[1, 2], так как f(1) = - 1 < 0 и f(2) = 5 > 0.

Уравнение (10) можно записать в виде

х = х3 - 1.	(11)

Здесь

j (х) = х³ - 1 и j' (х) = 3х²;

поэтому

j' (х) 3 при 1 х2

и, следовательно, условия сходимости процесса итерации не выполнены.

Если записать уравнение (10) в виде

	(12)

то будем иметь:

.

Отсюда при 1 х2 и значит, процесс итерации для уравнения (12) быстро сойдется.

Найдем корень ? уравнения (10) с точностью до 10^-2. Вычисляем последовательные приближения х_nс одним запасным знаком по формуле

Найденные значения помещены в Таблицу 1:

Таблица 1. Значения последовательных приближений x_i.

i	0	1	2	3	4
xi	1	1,260	1,312	1,322	1,3243

С точностью до 10^-2 можно положить ? = 1,324.



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

3.1 Приведение системы к виду, удобному для итераций

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

Ax = b

с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

x = Bx + c.

Здесь B - квадратная матрица с элементами b_ij (i, j = 1, 2, …, n), c - вектор-столбец с элементами c_ij(i = 1, 2, …, n).

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

x₁ = b₁₁x₁ + b₁₂x₂ + b₁₃x₃ + … + b_1nx_n + c₁

x₂ = b₂₁x₁ + b₂₂x₂ + b₂₃x₃ + … + b_2nx_n + c₂

. . . . . . . . . . . . . . . . .

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_nnx_n + c_n

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x₁:

x₁ = a₁₁-¹ (b₁ - a₁₂x₂ - a₁₃x₃ - … - a_1nx_n),

из второго уравнения - неизвестное x₂:

x₂ = a₂₁-¹ (b₂ - a₂₂x₂ - a₂₃x₃ - … - a_2nx_n),

и т. д. В результате получим систему

x₁ = b₁₂x₂ + b₁₃x₃ + … + b_1,n-₁x_n-₁ + b_1nx_n+ c₁ ,

x₂ = b₂₁x₁ + b₂₃x₃ + … + b_2,n-₁x_n-₁ + b_2nx_n+ c₂ ,

x₃ = b₃₁x₁ + b₃₂x₂ + … + b_3,n-₁x_n-₁ + b_3nx_n+ c₃ ,

. . . . . . . . . . . . . . . . . . . . . . .

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_n,n-₁x_n-₁ + c_n ,

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

b_ij = -a_ij / a_ii, c_i = b_i / a_ii (i, j = 1, 2, …, n, j ? i)

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

3.2. Описание метода

Введем нижнюю и верхнюю треугольные матрицы

0 0 0 … 0 0 b₁₂ b₁₃ … b_1n

b₂₁ 0 0 … 0 0 0 b₂₃ … b_2n

B₁ = b₃₁ b₃₂ 0 … 0 , B₂ = 0 0 0 … b_3n

. . . . . . . . . . . . . .

b_n1 b_n2 b_n3 … 0 0 0 0 … 0

Заметим, что B = B₁+ B₂ и поэтому решение x исходной системы удовлетворяет равенству

x = B₁x + B₂ x + c .

Выберем начальное приближение x⁽⁰⁾ = [x₁⁽⁰⁾, x₂⁽⁰⁾, …, x_n⁽⁰⁾]^T. Подставляя его в правую часть равенства при верхней треугольной матрице B₂и вычисляя полученное выражение, находим первое приближение

x⁽¹⁾ = B₁x⁽⁰⁾ + B₂x⁽¹⁾

Подставляя приближение x⁽¹⁾, получим

x⁽²⁾ = B₁x⁽¹⁾ + B₂x⁽²⁾

Продолжая этот процесс далее, получим последовательность x⁽⁰⁾, x⁽¹⁾, …, x⁽ⁿ⁾, … приближений к вычисляемых по формуле

x^(k+1) = B₁^(k+1) + B₂^(k) + c

или в развернутой форме записи

x₁^(k+1) = b₁₂x₂^(k) + b₁₃x₂^(k) + … + b_1nx_n^(k) + c₁ ,

x₂^(k+1) = b₂₁x₁^(k+1) + b₂₃x₃^(k) + … + b_2nx_n^(k) + c₂ ,

x₃^(k+1) = b₃₁x₁^(k+1) + b₃₂x₂^(k+1) + … + b_3nx_n^(k) + c₃ ,

. . . . . . . . . . . . . . . . . . . . . . . . . .

x_n^(k+1) = b_n1x₁^(k+1) + b_n2x₂^(k+1) + b_n3x₃^(k+1) + … + c_n .

Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим

x_i^(k+1) = x_i^(k) - a_ii-¹(?_j=1ⁱ-¹a_ijx_j^(k+1) + ?_j=1ⁿa_ijx_i^(k) - b_i).

Тогда достаточным условием сходимоти метода Зейделя будет

?_{j=1, j?i} ⁿ | a_ij | < | a_ii |

(условие доминированния диагонали).

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



4. Метод релаксации

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

Суть метода релаксации состоит в следующем. После вычисления очередной компоненты приближения по формуле метода Зейделя

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



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

Пусть корень уравнения f(x) = 0отделён на отрезке, причем f'(x) и f''(x) непрерывны и сохраняют определённые знаки при . Найдя какое-нибудь n-e приближение корня n (), мы можем уточнить его по Методу Ньютона следующим образом. Пусть,где hn малая величина. Отсюда, применяя формулу Тейлора, получим:

Следовательно,

Внеся эту поправку в формулу (2), получим следующее по порядку приближение корня:

(n=0,1,2…).

Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой y=f(x) касательной, проведенной в некоторой точке кривой. в самом деле, положим для определённости, что f''(x)>0 при и f(b)>0 (рис. 1).

Выберем, например, х0=b, для которого f(x)f''(x)>0. Проведем касательную к кривойy=f(x) в точке B0 (x0, f(x0)).

В качестве 1-го приближения x1 корня возьмем абсциссу точки пересечения этой касательной с осью Ox. Через точку B1(x1, f(x1)) снова проведем касательную, абсцисса точки пересечения которой с Oxдаст нам 2-е приближениеx2 корня и т.д. (рис. 1). Очевидно, что уравнение касательной в точке Bn (xn, f(xn)) (где n=0,1,2…) есть

Полагая, что у=0, x=xn+1,получим формулу (3):

.

Заметим, что если в нашем случае положить х0=a и, следовательно, f(x)f''(x)<0, то, проведя касательную к кривой y=f(x)в точкеA(a, f(a)), мы получили бы точку x1' (рис. 1), лежащую вне отрезка [а, b], т. е. при этом выборе начального значения метод Ньютона оказывается непрактичным. Таким образом, в данном случае «хорошим» начальным приближением х0 является то, для которого выполнено неравенство

(4)

Докажем, что это правило является общим.

Теорема. Если f(a)f(b)<0, причем f'(x) и f" (х) отличны от нуля и сохраняют определенные знаки при , то, исходя из начального приближения удовлетворяющего неравенству (4), можно вычислить методом Ньютона (формула (3)) единственный корень уравнения (1) с любой степенью точности.

Доказательство. Пусть, например, f(a)< 0, f(b)>0, f'(x)>0, f''(x)>0 при (остальные случаи рассматриваются аналогично). Согласно неравенству (4) имеем f(x0) >0 (например, можно принять х0 = b).

Методом математической индукции докажем, что все приближения xn>(n = 0, 1, 2,...) и, следовательно, f(xn)>0. В самом деле, прежде всего, x0 >.

Пусть теперь xn>. Положим

Применяя формулу Тейлора, получим:

где <cn<xn.

Так как f''(x)>0, то имеем:

и, следовательно,

что и требовалось доказать.

Из формулы (3), учитывая знаки f(xn) и f'(хn), имеем хn+1 < хn (n = 0, 1, ...), т. е. последовательные приближения x0, x1,…, хn, ... образуют ограниченную монотонно убывающую последовательность. Следовательно, существует .

Переходя к пределу в равенстве (3), будем иметь:

т.е. f()=0. Следовательно, =, что и требовалось доказать.

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

Замечание 1. Если:

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

2. f(a)f(b)<0;

3. f'(x)при;

4. f"(x) существует всюду и сохраняет постоянный знак, то при применении метода Ньютона для нахождения корня уравнения f(x) = 0, лежащего в интервале (а, b), за начальное приближение x0 можно принять любое значение . В частности, можно взять x0=a или x0=b.

Действительно, пусть, например, f'(x) > 0 при , f"(x )>0 и х0 = с, где .

Если f(с) = 0, то корень = с и задача, таким образом, решена.

Если f(c) > 0, то справедливо приведенное выше рассуждение и процесс Ньютона с начальным значением с сходится к корню.

Наконец, если f(с) <0, то находим значение

Применяя формулу Тейлора, будем иметь:

где --некоторое промежуточное значение между с и х1. Таким образом,f(x1)f''(x1)>0.

Кроме того, из условия f"(x)>0 вытекает, что f' (х) -- возрастающая функция и, значит, f'(x) >f' (а) > 0 при х>а. Следовательно,х1можно принять за начальное значение для процесса Ньютона, сходящегося к некоторому корнюфункции f(x) такому, что>с а. Так как в силу положительности производной f'(х) при х > а функция f(x) имеет единственный корень на интервале (а, +), то=.

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

Замечание 2. Из формулы (3) видно, что чем больше численное значение производной f'(x) в окрестности данного корня, тем меньше поправка, которую нужно прибавить к n-му приближению, чтобы получить (n+l)-e приближение. Поэтому метод Ньютона особенно удобно применять тогда, когда в окрестности данного корня график функции имеет большую крутизну. Но если численное значение производной f'(x)близ корня мало, то поправки будут велики, и вычисление корня по этому методу может оказаться очень долгим, а иногда и вовсе невозможным. Следовательно, если кривая y=f(x) вблизи точки пересечения с осью Ох почти горизонтальна, то применять метод Ньютона для решения уравнения f(x) = 0 не рекомендуется.

Оценка погрешности

Для оценки погрешности n-го приближения хn можно воспользоваться общей формулой.

(6)

где m1 -- наименьшее значение |f'(x)|на отрезке [а, b].

Выведем еще одну формулу для оценки точности приближения xn. Применяя формулу Тейлора, имеем:

(7)

где .Так как в силу определения приближения хп имеем

то из (7) находим:

где М2 -- наибольшее значение |f" (х)|на отрезке [а, b].Следовательно, на основании формулы (6) окончательно получаем:

Если процесс Ньютона сходится, то хп- хп-10 при п-->. Поэтому при пимеем:

т.е. «установившиеся» начальные десятичные знаки приближений xn-1иxnначиная с некоторого приближения, являются верными.

Заметим, что в общем случае совпадение с точностью до е двух последовательных приближений хп-1и хпвовсе не гарантирует, что с той же точностью совпадает значение хп и точный корень | (рис. 19).

Установим также формулу, связывающую абсолютные погрешности двух последовательных приближений хп и xn+1. Из формулы (5) получаем:

где . Отсюда, учитывая формулу (3), будем иметь:

и, следовательно,

(9)

Формула (9) обеспечивает быструю сходимость процесса Ньютона, если начальное приближение х0 таково, что

В частности, если

то из формулы (9) получаем:

т.е. в этом случае, если приближение хп имело mверных десятичных знаков после запятой, то следующее приближение хп+1 будет иметь по меньшей мере 2т верных знаков; иными словами, если , то с помощью метода Ньютона число верных знаков после запятой искомого корня удваивается на каждом шаге.



6. Метод наискорейшего градиентного спуска

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

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

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

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

и

Обозначим через, т.е. положим

Пусть. Вспоминая, что, вычислим. Имеем

Откуда

На рис. 6.8.1 изображены последовательные приближения метода наискорейшего спуска и линии уровня функции F. Итерационный процесс (3), (4) называют методом наискорейшего спуска решения рассматриваемой системы линейных уравнений.

Рис. 6.8.1

Пусть собственные значения матрицы А расположены на, т. е.

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

Доказательство. При произведем одну итерацию оптимального одношагового итерационного процесса

Погрешности итераций связаны соотношением

Пусть - ортонормированная система собственных векторов матрицы . Поскольку, то при всех выполняются соотношения

и, таким образом,

Пусть. Справедливы соотношения

С учетом (7) получаем

Поскольку, то это означает, что

Приближение можно записать в виде (1)

Так как на достигается минимум среди всех приближений вида (1), то. Отсюда следует оценка

а поэтому и справедливость утверждения теоремы. Аналогично (7.9) можно получить неравенство

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

Однако есть принципиальное различие в этих методах. Для написания итерационного процесса (6) требуется информация о границах спектра. В случае метода (3), (4), такой информации не требуется.

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

У метода наискорейшего спуска (3), (4), однако, есть следующий недостаток по сравнению с простейшим процессом (6). При нахождении каждого следующего приближения он требует не одной, а двух трудоемких операций умножения матрицы на вектор.

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

Вектор называется невязки. Умножая (8) слева на А и вычитая, получим

Формулу (4) для определения можно записать в виде

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

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

Задача 1. Получить оценку скорости сходимости метода наискорейшего спуска

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

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

Иначе обстоит дело в случае метода наискорейшего спуска. Пусть, например, -- единичная матрица. Тогда

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

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

Размещено на Allbest.ru

...