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

⇐ ПредыдущаяСтр 5 из 8Следующая ⇒

Рассмотрим задачу отыскания максимального по модулю собственного значения матрицы А. По определению собственные значениями квадратной матрицы 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 ,

λ ,

где . Итерационный процесс прекращается, когда будет выполнено условие: | λ ⁽ⁿ⁾ - λ ⁽ⁿ^-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⁽ⁿ^-1) и V_n A⁽ⁿ^-1) = B отличаются лишь k –й и l –й строками, т. к. эти матрицы B являются линейными комбинациями тех же строк матрицы A⁽ⁿ^-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⁽ⁿ^-1)…M⁽²⁾M⁽¹⁾A, вектор правой части g=M⁽ⁿ^-1)…M⁽²⁾M⁽¹⁾f.

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

, i= n-1, …, 1.

⇐ Предыдущая 1 2 3 456 7 8 Следующая ⇒