Формула (3.7) и есть итерационная формула метода Ньютона для приближенного решения системы нелинейных уравнений.

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

 

f¢(x^(n))*Dx^(n+1) =-f(x^(n)).

(3.8)

 

Это система линейных алгебраических уравнений относительно поправки Dx⁽ⁿ⁺¹⁾= x⁽ⁿ⁺¹⁾- x⁽ⁿ⁾. Затем полагают

 

x^(^n+1)=x^(^n)+Dx^(^n+1).

(3.9)

 

Сходимость метода

 

Теорема. Пусть в некоторой окрестности решения х системы (3.1) функции f_i (при i= ) дважды непрерывно дифференцируемы и матрица Якоби не вырождена. Тогда найдется такая малая d окрестность вокруг решения х, что при выборе начального приближения x ⁰ из этой окрестности итерационный метод (3.7) не выйдет за пределы этой окрестности решения и справедлива оценка вида

,

 

где n - номер итерации.

Метод Ньютона сходится с квадратичной скоростью. На практике используется следующий критерий остановки:

 

.

Решение проблемы собственных значений

 

 

Пусть дана квадратная матрица A размерностью (m*m) и существует такое число l, что выполняется равенство

 

,

 

тогда такое число l называется собственным значением матрицы А, а x – соответствующим ему собственным вектором.

Перепишем это равенство в эквивалентной форме

 

(A - lE) * = 0.

(4.1)

 

Система (4.1) - однородная система линейных алгебраических уравнений. Для существования нетривиального решения системы (4.1) должно выполняться условие

 

det(A - lE) = 0.

(4.2)

 

Определитель в левой части уравнения является многочленом m-ой степени относительно l, его называют - характеристическим определителем (характеристическим многочленом). Следовательно, уравнение (4.2) имеет m корней или m собственных значений. Среди них могут быть как действительные, так и комплексные корни.

Задача вычисления собственных значений сводится к нахождению корней характеристического многочлена (4.2). Корни могут быть найдены одним из итерационных методов (в частности методом Ньютона).

Если найдено некоторое собственное значение матрицы A, то подставив это число в систему (4.1) и решив эту систему однородных уравнений, находим собственный вектор х, соответствующий данному собственному значению.

Собственные вектора будем при нахождении нормировать (вектор х умножаем на || х ||^-1, и таким образом они будут иметь единичную длину), нахождение собственных значений матрицы A и соответствующих им собственных векторов и есть полное решение проблемы собственных значений. А нахождение отдельных собственных значений и соответствующих им векторов - называется решением частной проблемы собственных значений.

Эта проблема имеет самостоятельное значение на практике.

Например, в электрических и механических системах собственные значения отвечают собственным частотам колебаний, а собственные вектора характеризуют соответствующие формы колебаний.

Эта задача легко решается для некоторых видов матриц - диагональных, треугольных и трехдиагональных матриц.

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

Пример 1. Матрица А – диагональная . Тогда

det(А-lЕ)= , а характеристическое уравнение имеет трехкратный корень l=а.

Собственными векторами для матрицы А будут единичные векторы

 

Пример 2. Найдем собственные числа матрицы

 

.

 

Составим характеристический многочлен

 

 

Используя метод Ньютона, определим один из корней уравнения Р₃(l)=0, а именно l₁» -7.87279.

Разделив многочлен на (l-l₁) получим многочлен второй степени: =l² + 3.02711l + 2.66765. Решив квадратное уравнение, находим оставшиеся два корня:l_2,3» -1.51356 ± 0.613841 * i (комплексное сопряженные корни).

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

Прямые методы

4.1.1 Метод Леверрье

 

Метод разделяется на две стадии:

- раскрытие характеристического уравнения,

- нахождение корней многочлена.

 

Пусть det(A-lE) - есть характеристический многочлен матрицы А ={a_ij} (i,j=1,2,…,m), т.е. , и l₁,l_2,…,l_m - есть полная совокупность корней этого многочлена (полный спектр собственных значений).

Рассмотрим суммы вида (k=1,2,…,m), т.е.

 

,

(4.3)

где - след матрицы.

В этом случае при k£m справедливы формулы Ньютона для всех (1£k£ m)

,

(4.4)

 

Откуда получаем

при k=1 р1 = -S1 , при k=2 р2 = -1/2 * (S2 + р1*S1), .............. при k=m рm = -1/n * (Sm + р1*Sm-1 + р2*Sm-2 +... + рm-1*S1).

(4.5)

 

Следовательно, коэффициенты характеристического многочлена р _i можно определить, если известны суммы S₁,S₂,...,S_m. Тогда схема алгоритма раскрытия характеристического определителя методом Леверрье будет следующей:

1) вычисляем степень матрицы: А^к=А^к-1*А для k=1,…,m;

2) определяют S_k - суммы элементов стоящих на главной диагонали матриц А^к;

3) по формулам (4.5) находят коэффициенты характеристического уравнения р_i (i=1,2,…,m).

4.1.2 Усовершенствованный метод Фадеева

 

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

1) вычисляют элементы матриц A₁,A₂,..,A_m:

 

 

(в конце подсчета B_m нулевая матрица для контроля);

 

2) определяют коэффициенты характеристического уравнения р_i

q₁ = -р₁, q₂ = -р₂,..., q_m = -р_m.

Существуют и другие методы раскрытия характеристического определителя: метод Крылова, Данилевского и др.

 

4.1.3 Метод Данилевского

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

 

B=S^-1*AS,

 

если это равенство справедливо, то матрицы A и B подобны, а само преобразование называется преобразованием подобия (переход к новому базису в пространстве m - мерных векторов).

Пусть y - результат применения матрицы A к вектору х

 

y =A* х.

 

Сделаем замену переменных:

 

x =S* x ', y =S* y'.

 

Тогда равенство y =A* х преобразуется к виду

 

y' =S^-1*A*S* x'.

 

В этом случае матрица B и матрица A имеют одни и те же собственные числа. Это можно легко увидеть раскрыв определитель

 

.

Следовательно, матрицы A и B - подобные, имеют одни и те же собственные значения. Но собственные векторы х и х’ – не совпадают, они связаны между собой простым соотношением

 

х = S* х '.

 

Такую матрицу A с помощью преобразования подобия или же последовательности таких преобразований можно привести к матрице Фробениуса вида:

.

 

Детерминант матрицы F det (F) можно разложить по элементам первой строки:

 

.

 

Тогда коэффициенты характеристического многочлена матрицы А будут р₁ = f₁₁ , p₂ = f_12,…, p_n = f_1m.

 

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

.

 

Тогда собственными числами будут диагональные элементы матрицы B:

 

.

 

Третий случай. Матрицу A с помощью преобразования подобия можно привести к Жордановой форме

 

,

 

где l_i - собственные числа матрицы A; S_i - константы (0 или 1); если S_i=1, то l_i=l_i+1.

 

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

 

,