Метод скалярных произведений

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

Ax= λ x, (5.1)

где x - собственный вектор. Собственный вектор x_i (i=1,…,n), соответствующий собственному значению λ_i, является решением однородной системы линейных алгебраических уравнений

(A – λ E) x = 0.

Пусть матрица A размерности m´ m имеет полную систему нормированных собственных векторов е_i (I=1,…,m), т. е. || е_i ||=1, и пусть

| λ₁| > | λ₂| ³ … ³ | λ_m| ³ 0.

Зададим вектор

.

Будем последовательно вычислять векторы по итерационной формуле

xⁿ⁺¹ =Axⁿ.

Тогда xⁿ можно записать следующим образом:

.

Представим это равенство в виде

xⁿ =c₁λⁿe₁ +o(|λ|ⁿ).

Тогда имеем

(xⁿ, xⁿ)=| c₁|² | λ₁|²ⁿ + o(|λ₁|ⁿ|λ₂|ⁿ).

(xⁿ⁺¹, xⁿ)= λ₁| c₁|² | λ₁|²ⁿ + o(|λ₁|ⁿ|λ₂|ⁿ).

Находим:

,

 

при этом

λ =λ+O .

В процессе итераций при n , ||x || , если |λ |>1, ||x || 0, если |λ |<1, поэтому всегда найдется такое n, что в ЭВМ произойдет АВОСТ, если (при |λ |<1) x станет нулем. Чтобы этого не случилось, рекомендуется использовать следующий алгоритм:

e = ,

x =Ae ,

λ ,

где . Итерационный процесс прекращается, когда будет выполнено условие: | λ⁽ⁿ⁾ - λ^(n-1)| ≤ε.

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

Иногда причиной плохой сходимости итераций может быть то, что начальное приближение x⁽⁰⁾ оказалось ортогональным собственному вектору, соответствующему максимальному по модулю собственному значению. В этом случае рекомендуется сменить начальное приближение.

Для нахождения минимального собственного значения матрицы А, найдем матрицу B= (A - λ₁E) и применим для нее итерационный процесс для нахождения максимального по модулю собственного значения | λ₁(B)|.

Если λ₁(A) >0, то, очевидно, что λ_i (B)= λ_i (A)- λ₁ (A) ≤ 0, i=1,2,…,m. Поэтому λ ₁(B)= min(λ_i(A) - λ₁(A))= min λ_i(A) - λ₁(A), то есть minλ_i (A)= λ₁(A)+λ₁(B).

Если λ₁(A) <0, то max λ_i(A)=min λ_i(A)+ λ₁(B).

Метод вращения

Любую действительную, симметричную матрицу A можно привести к виду A = U ∙D ∙U^–1 , где U – ортогональная матрица (U ^–1 = U ^T ),

D – диагональная матрица,

где λ_i – собственные значения матрицы A.

Следовательно, имеем U^–1 ∙A ∙U = D.

На этом свойстве матрицы основан метод вращения: если некоторым ортогональным преобразованием V свести матрицу A к диагональной: , то собственные значения матриц совпадают.

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

Итак, по заданной матрице A будем строить последовательность A^k так, чтобы A^k-1 находилась через A^k при помощи преобразования подобия со следующей матрицей вращения:

Пусть нашли . Найдем . Пусть это будет , k<l (i, j = 1,…,m), и выбираем угол по формуле

.

Строится ортогональная матрица V_n, которая отличается от единичной матрицы E только элементами:

,

,

и делается преобразование подобия

.

При этом матрицы A^(n-1) и V_n A^(n-1) = B отличаются лишь k –й и l –й строками, т. к. эти матрицы B являются линейными комбинациями тех же строк матрицы A^(n-1):

,

.

Аналогично k –й и l -й столбцы матрицы A⁽ⁿ⁾:

,

.

Элементы являются приближенными к собственным числам λ_i матрицы A, а столбцы матрицы

являются приближенными к собственным векторам матрицы A. При этом имеет место оценка погрешности

.

 

Задания

1. С помощью метода скалярных произведений найти максимальное по модулю и минимальное по модулю собственное значение и соответствующие им собственные вектора для симметричной матрицы A с заданной точностью ε. Провести расчеты при различных начальных приближениях x⁽⁰⁾.

2. С помощью метода вращения найти все собственные значения и соответствующие им собственные вектора для симметричной действительной матрицы A с заданной точностью ε.

Варианты матриц

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

 

Тест: ,

λ ₁= -4,2841, x₁ = (-0,597; -0,746; 1),

λ₂ = 3,7621, x ₂= (1; -0,492; 0,423),

λ₃ = 5,522, , x ₃= (-0,00858; 0,228; 1).

Тема 6. Решение систем линейных алгебраических уравнений

Обусловленность матрицы

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

 

Определение. Говорят, что задача поставлена корректно, если ее решение существует, единственно и непрерывно зависит от входных данных.

Рассмотрим систему

A x = f , (6.1)

где А - квадратная, неособенная матрица размерности n, и, следовательно, det(A) ≠ 0, тогда существует единственное решение системы. Чтобы убедиться в корректности задачи (6.1) необходимо еще установить непрерывную зависимость решения от входных данных. Входными данными являются правая часть f и элементы матрицы А.

Соответственно, различают устойчивость по правой части, когда возмущается только правая часть f , а матрица А остается неизменной, и коэффициентную устойчивость, когда возмущается только матрица А .

Будем считать, что решение и правая часть задачи (6.1) принадлежат линейному пространству H, состоящему из n-мерных векторов. Введем в H норму, для которой выполнено:

||x||>0, для всех х≠0 H ,

||α x||=| α| ||x||, для любого числа А и х H ,

||x+y||≤||x||+||y||, для любых x и y H .

Определение. Нормой матрицы А, подчиненной данной норме векторов, называется число , для всех х≠0 H .

Наряду с системой (6.1) рассмотрим «возмущенную» систему A x_ε = f_δ , которая отличается от (6.1) правой частью. Насколько сильно может измениться решение х в результате изменения правой части?

Обозначим δx=x - x_ε,, δf=f - f_δ.

Определение.Говорят, что система (6.1) устойчива по правой части, если при любых f и f_δ справедлива оценка || δx||≤ M || δf ||, где M - постоянная, M >0.

 

Эта оценка выражает факт непрерывной зависимости решения от правой части, то есть показывает, что || δx|| стремится к нулю при || δf ||стремящемся к нулю. Наличие устойчивости очень важно при численном решении систем уравнений, так как никогда нельзя задать правую часть f точно. Погрешность δf возникает в результате округления.

Получим оценку для относительной погрешности решения . Используем неравенство ||f|| ≤ ||A|| ||x|| . Перемножим его с неравенством ||δx||≤ ||A^-1|| || δf ||, получим требуемую оценку

.

 

Определение. Число ρ(A)= называется числом обусловленности матрицы A и характеризует степень зависимости относительной погрешности решения от относительной погрешности правой части. В случае самосопряженной матрицы A =A^* это число равно

ρ(A)= ,

где λ_max , λ_min – максимальное и минимальное по модулю собственные значения матрицы A.

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

Например, для матрицы

число обусловленности ρ(A)= , и если взять за правую часть системы вектор f= (1,0000, 1,0000)^T, то получим решение x=(0,3333, 0,0000)^T. Решение «возмущенной» системы с правой частью f_δ = (0,9998, 1,0000)^T равно x_ε=(5,0000, 2,0000)^T.

Если взять матрицу

и за правую часть системы вектор f= (1,0000, 0)^T, то получим решение . Решение «возмущенной» системы при изменении коэффициента a₂₂ = 0,421 на 0,433 равно x_ε = (47,983, -86,879)^T.

 

Метод Гаусса

Метод Гаусса относится к классу точных методов, т. е. точное решение можно найти за конечное число арифметических операций, в предположении, что нет ошибок округления. В методе Гаусса число арифметических операций равно (2/3)∙m³. Любую матрицу A можно представить в виде произведения верхнетреугольной V и нижнетреугольной L матриц:

A=L∙V.

Если зафиксировать главную диагональ у верхнетреугольной (нижне-треугольной) матрицы, то такое разложение единственно и тогда решение системы можно разбить на два этапа:

- нахождение матриц L и V;

- решение СЛАУ Ly=f и Vx=y.

Метод Гаусса включает прямой ход - исключения неизвестных, и обратный ход - нахождения решения.

Рассмотрим решение СЛАУ Ax=f , состоящее из n неизвестных.

(6.2)

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

Шаг 1. Разделим первое уравнение на a₁₁≠ 0 , из второго вычитаем первое, умноженное на a₂₁ , из третьего вычитаем первое, умноженное на a₃₁ , и т. д.

Получим

На этом 1- й шаг исключения завершен.

Далее рассмотрим систему:

И аналогичным образом исключим неизвестное x₂. Получим систему вида

Таким образом, на каждом k -м шаге будем исключать переменную x_k (k = 1,2,…, n-1) по следующему алгоритму:

Получим СЛАУ:

Обозначим матрицу коэффициентов V=M^(n-1)…M⁽²⁾M⁽¹⁾A, вектор правой части g=M^(n-1)…M⁽²⁾M⁽¹⁾f.

Этап II метода Гаусса (обратный ход метода) состоит в нахождении решения СЛАУ Vx=g из системы с верхнетреугольной матрицей :

,

, i= n-1, …, 1.