ПОНЯТИЕ О МЕТОДЕ РЕЛАКСАЦИИ

Пример.

Метод хорд = Метод ложного положения = метод линейной интерполяции = метод пропорциональных частей

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

f(x)=0 (1),

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

Требуется найти корень уравнения x с заданной степенью точности e.

1. Пусть функция непрерывна на отрезке [a,b], , B- неподвижная точка, x₀=a.

a=x₀

x₁

x₂

-уравнение секущей.

Найдем точку пересечения с осью 0x (). Тогда , или

Продолжая процесс, получим итерационную формулу

2. Пусть функция непрерывна на отрезке [a,b], , А- неподвижная точка, x₀=b.

-уравнение секущей.

Найдем точку пересечения с осью 0x (). Тогда , или

, или

Метод Ньютона (метод касательных) нахождения корней

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

f(x)=0 (1),

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

Требуется найти корень уравнения x с заданной степенью точности e.

b=x₀

x₁

x₂

1. Рассмотрим касательную к кривой y=f(x) в точке x₀. Она задается уравнением . Пересечение с осью 0x происходит при y=0.

Тогда , или .

Продолжая процесс, получим рекуррентную формулу .

Теорема. Если функция является непрерывной вместе со своей второй производной на отрезке [a,b] и на концах отрезка функция имеет разные знаки, причем вторая производная на этом отрезке не меняет знака, то уравнение f(x)=0 имеет единственный корень x.

Дано: f(x)ÎС₂[a,b], f(a)×f(b)<0, не меняет знака на отрезке [a,b].

Доказать, что уравнение f(x)=0 имеет единственный корень x.

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

Покажем, что корень - единственный. Предположим, что уравнение имеет два различных корня на отрезке [a,b]: x₁ ¹x₂. Это означает, что f(x₁)= f(x₂)=0. Тогда по теореме Ролля (следствие теоремы Лагранжа) существует такая точка cÎ[x₁, x₂], что .

Рассмотрим случай, когда , то есть - возрастает на отрезке [a,b] и . Тогда на отрезке [a,c] функция f убывает и f(a)>f(x₁)=0; на отрезке [c,b] функция f возрастает и f(b)>f(x₂)=0. Оба конца отрезка оказались положительны, что противоречит условию теоремы. Противоречие возникло из предположения о том, что уравнение имеет два различных корня на отрезке [a,b]. Значит, корень единственный.

Алгоритм метода:

1. Отделяем корень.

2. Определяем знак второй производной: .

3. Выбираем в качестве тот конец отрезка [a,b], знак функции f в котором бы совпадал со знаком .

4. Применяем формулу .

Оценим погрешность k-ого приближения метода Ньютона. По формуле Тейлора

, сÎ[x;x_k].

Поделим обе части равенства на .

Из формулы Ньютона , поэтому .

Обозначим , . Тогда

Обозначим . Тогда

, и

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

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

Пример.

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

Пусть Û , где , .

Предположим, что существует решение и .

Пусть -некоторое приближение x и +d_k=x. Разложим в ряд . Разложим в ряд Тейлора .

Здесь -якобиан функции f(X).

Если пренебречь и учесть, что , то

Þ .

Пусть согласно новому методу .

Тогда .

Алгоритм метода:

1. Выбираем приближенно (найдено ).

2. Находим ,

3. Решаем СЛАУ либо находим .

4. Находим .

Теорема. Для того, чтобы у системы существовало, и притом единственное решение , необходимо и достаточно, чтобы определитель матрицы Якоби

Пусть имеется некоторая точка X в окрестности x решения системы (1). Пусть функция f в окрестности 1) является гладкой в том смысле, что существуют производные функции f до второго порядка включительно такие, что ; 2) матрица Якоби f(X) равномерно невырождена, то есть .

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

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

1) ;

2) .

3) Рассмотрим

4) Þ

Пример

Решение систем линейных алгебраических уравнений (СЛАУ)

Рассмотрим систему линейных алгебраических уравнений:

(1)

Выпишем матрицу коэффициентов при неизвестных:

и два вектора

Тогда систему (1) можно записать в матричной форме

Квадратная матрица А называется невырожденной, или неособенной, если det A=|A|¹0.

Если матрица A коэффициентов при неизвестных СЛАУ невырождена, то система имеет единственное решение.

СЛАУ

Совместная (существует хотя бы одно решение)

Несовместная (противоречивая) не имеет решений

Определенная (единственное решение

Неопределенная (более одного решения)

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

точные (прямые) и приближенные.

1. Точные алгоритмы позволяют получить решение за конечное число арифметических действий. К ним относятся: метод Гаусса, метод Крамера, метод прогонки, метод квадратных корней.

2. Приближенные методы: метод простой итерации, метод Зейделя, метод релаксации.

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

Метод Гаусса (схема единственного деления).

Существуют различные вычислительные схемы, реализующие этот метод. Рассмотрим схему единственного деления. Предположим, что (в противном случае меняем строки №1 и №k местами, , либо столбцы №1 и №k местами, ). В полученной системе поделим первое уравнение на . Полученное уравнение умножим сначала на , затем на и результаты соответственно вычитаются из 2, 3, и 4 уравнений. Тогда получим новую систему, содержащую 3 уравнения с 3 неизвестными.

Поступая аналогично с полученной системой, мы исключим неизвестную .

Аналогично из последней системы исключаем .

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

Номер раздела	i	a_i1	a_i₂	a_i₃	a_i₄	a_i₅	a_i6= a_i1+ a_i2+ a_i3+ a_i4+ a_i5 ₍_Сумма)
I		a₁₁	a₂₂	a₁₃	a₁₄	a₁₅	a₁₆
	a₂₁	a₂₂	a₂₃	a₂₄	a₂₅	a₂₆
	a₃₁	a₃₂	a₃₃	a₃₄	a₃₅	a₃₆
	a₄₁	a₄₂	a₄₃	a₄₄	a₄₅	a₄₆
			b₁₂	b₁₃	b₁₄	b₁₅	b₁₆= a₁₆/ a₁₁=1+ b₁₂+ b₁₃+ b₁₄+ b₁₅
II


							= / =1+ + +
III

							= /
IV
					x₄
						x₃
						x₂
						x₁

Порядок заполнения таблицы.

Прямой ход

1. Записываем коэффициенты данной системы в четырех строках и 5 столбцах раздела I

2. Суммируем все коэффициенты по строке и записываем их в столбце «Сумма» (столбец контроля).

3. Делим все числа 1 строки на a₁₁ и результат записываем в 5 строку раздела I.

4. Вычисляем сумму b₁_j, j=1..5, если вычисления ведутся с постоянным знаком после запятой, то числа b₁₆ и не должны отличаться более, чем на 1 последнего разряда.

5. Вычисляем коэффициенты и результаты записываем в первые 3 строки раздела II.

6. Делаем проверку. Сумма элементов каждой строки раздела II ()должна совпадать с .

7. Делим элементы строки 2 раздела II на , и результаты записываем в последнюю строку раздела II.

8. Делаем соответствующую проверку.

9. Аналогично заполняем и проверяем III, IV разделы.

Обратный ход.

1. В разделе V записываем 1 (как показано в схеме).

2. Вычисляем .

3.Для вычисления x₃, x₂, и x₁ используются последние строчки разделов 3, 2, 1, содержащие 1.

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

Если - решение исходной системы, а - решение контрольной системы, то = +1.

Последний контроль осуществляется только с помощью столбца «Сумма».

Вычисление определителя.

С помощью схемы единственного деления можно вычислить определитель матрицы A. Пусть Операции по исключению определитель не изменяют, изменяет только деление на a₁₁, , , - определитель изменится и станет равным . С другой стороны, определитель треугольной матрицы равен 1. Тогда и .

Обращение матрицы.

Пусть дана матрица A.

Определение. Матрица A^-1 называется обратной по отношению к матрице A, если , где E- единичная матрица.

Определение. Квадратная матрица A называется неособенной (невырожденной), если detA=|A|¹0.

Теорема. Всякая невырожденная матрица имеет обратную.

Рассмотрим случай отыскания матрицы, обратной матрице A, размерностью 4´4.

, ,

Данную систему можно представить в виде совокупности четырех СЛУ:

, , , .

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

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

Метод Крамера.

Алгоритм:

1. Вычисляем определитель матрицы A.

2. Для того, чтобы найти компоненту решения x_i, необходимо поделить определитель матрицы, полученной путем замены i- го столбца столбцом свободных членов на определитель матрицы А.

Доказательство: см. курс алгебры.

Приближенные методы.

1. Неподвижная точка оператора.

Определение. Операторºфункция, в общем случае отображение пространства в себя называется оператором; функционал f: (M,r)®(R, r₁).

Определение. Множество М называется линейным пространством, если выполняются следующие аксиомы:

1. x+y=y+x

2. (x+y)+z=x+(y+z) ассоциативность слож

3. ($ 0ÎM) (x+0=0+x=x).

4. "xÎM ($ -xÎM) x+(-x)=0

5. 1×x=x

6. " l, m ÎR (lm)x=l(mx) ассоциативность умн

7. " l, m ÎR l (x+y)= x+ly; (l+m)x=lx+mx

Определение. Пусть задан оператор f: М®M. Тогда точка a называется неподвижной точкой оператора f, если f(a)=a.

Примеры неподвижных точек: корень уравнения, тождественное преобразование – все точки неподвижные; поворот ; симметрия S_l относительно прямой l, l- неподвижная точка.

Определение. Пусть дан оператор f: М®M, на множестве М введена метрика r. Тогда f есть оператор сжатия, или сжимающееся отображение, если ($a) (0<a<1 Þ ("xÎM) ("yÎM) (r(f(x),f(y))£a ×r(x,y))

Определение. Последовательность точек метрического пространства (M,r) называется фундаментальной, если она удовлетворяет условию Коши:

для любого существует такое натуральное n₀, что r(x_n,x_m)<e для всех n, m>n₀.

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

Теорема Банаха. Достаточный признак существования неподвижной точки.

Пусть (M,r) - полное метрическое пространство. В нем задан оператор f: М®M, f - оператор сжатия. Тогда .

Доказательство. Возьмем произвольную точку x₀ÎM. Рассмотрим последовательность и покажем, что:

1) -сходящаяся последовательность. Обозначим . Тогда

Найдем такое n₀, чтобы выполнялось неравенство .

Тогда

Получили:

-фундаментальная последовательность, а значит, она сходится к некоторой точке a.

2) Покажем, что a - неподвижная.

В правой части перейдем к пределу при n®¥.

Тогда

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

® и

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

Аналог теоремы Банаха.

Пусть (M, r)- линейное полное метрическое пространство, f - некоторый линейный оператор, . Тогда существует, и притом единственная неподвижная точка оператора f. .

Доказательство.

Таким образом, f - сжимающееся отображение.

Замечание 1.

Определение. Нормой оператора A в нормированном пространстве M называется

Норма оператора A согласована с нормой, введенной в пространстве M.

Следствие. .

Погрешность.

Þ Þ

; Þ

Замечание 2.

Пусть A-матричный оператор, т.е. A- матрица, .

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

1) ;

2) ;

3) ;

Метод простой итерации для СЛУ

Пусть дана некоторая СЛУ. Её необходимо привести к виду X=A×X+B, или , . Если одна из вышеперечисленных норм окажется меньше 1, то итерационный процесс сходится (на основании теоремы Банаха).

Метод Якоби.

Пусть необходимо решить систему вида . Представим A=L+D+R, где D - диагональная матрица, L и R - соответственно левая и правая строго треугольные матрицы (т.е. с нулевой диагональю). Тогда Û Û . Пусть и . Тогда Û . Основанный на таком приведении метод простой итерации называется методом Якоби.

Определение. Диагональное преобладание означает, что .

Теорема. В случае диагонального преобладания в матрице А системы метод Якоби сходится.

Определение 1. Пусть дана матрица А. Рассмотрим уравнение AX=lX. Тогда X¹0 называется собственным вектором матрицы А или собственным вектором данного линейного преобразования, а число l называется собственным значением.

Определение 2. Уравнение вида называется характеристическим уравнением матрицы А. Из этого уравнения находятся собственные числа (значения) l.

Теорема. Для сходимости метода простой итерации при любом начальном векторе к решению системы необходимо и достаточно, чтобы все собственные числа матрицы B были по модулю меньше 1.

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

Итерационный процесс для метода Зейделя можно представить следующей последовательностью:

® ®

В связи с такой интерпретацией метод Зейделя называют методом последовательных смещений, а МПИ - одновременных смещений.

Тогда метод Зейделя есть Û Û Û , что есть метод простой итерации (при условии, что L+D -обратима). Поэтому можно переформулировать ряд утверждений, справедливых для МПИ.

Теорема. Для сходимости метода Зейделя необходимо и достаточно, чтобы все корни уравнения

были по модулю меньше 1.

Доказательство. det((L+D)l+R)=0 Û Û

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

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

Доказательство. Метод Зейделя равносилен МПИ при , а для него справедливы указанные оценки.

Определение. Матрица А называется симметричной тогда и только тогда, когда , j,i= .

Определение. Линейный оператор А называется:

1) положительным, если

2) положительно определенным, если

3) неотрицательным, если

Определение. Система называется нормальной, если матрица А- симметричная положительно определенная.

Теорема. Для существования единственного решения системы и сходимости метода Зейделя достаточно выполнения хотя бы одного из двух условий:

1) матрица А -нормальная;

2) , i = (диагональное преобладание)

Замечание. Для применения этой теоремы необходимо, чтобы диагональные элементы матрицы А . Каждое i-ое уравнение делится на . Все неизвестные, кроме , переносятся вправо и переходим к эквивалентной системе X=CX+D, где , при j¹i; c_ij=0 при j=i

Доказательство.

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

Лемма. Если A- симметричная матрица, то L=R^T и R=L^T.(ПРОВЕРИТЬ!)

Пусть и -собственные значения матрицы N, а и -соответствующие им собственные векторы. Тогда Þ Þ

1) Рассмотрим скалярные произведения и .

Они будут представляться в виде I

= = II

2) Учтем, что из коммутативности скалярных произведений и симметричности матрицы A следует:

3) Из II имеем = = = =

Þ = Ú.

4) Тогда из I и последнего полученного равенства имеем систему:

= Ú

5) Система равносильна следующей системе:

Откуда

6) Тогда

= + = =

= = =

Положим здесь i=j, тогда найдем: = =

Так как A - положительно определенная, то 1) >0; 2) диагональные элементы матрицы A положительны, то есть . Значит, обе части равенства положительны; ; >0 и . Откуда .

Заметим, что , так как если =1, то найдется , такое, что и Û Û Û Û =q.

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

2) Покажем, что при диагональном преобладании метод Зейделя сходится. Для этого сравним процесс Зейделя с методом простой итерации и убедимся, что процесс Зейделя сходится быстрее, чем МПИ.

Пусть

(норма). В силу диагонального преобладания m<1. Обозначим , . Тогда процесс Зейделя равносилен методу простой итерации с вычислительной схемой , а вычислительная схема метода Зейделя .