![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Метод скалярных произведений
Рассмотрим задачу отыскания максимального по модулю собственного значения матрицы А. По определению собственные значениями квадратной матрицы A называются числа, удовлетворяющие соотношению Ax= λ x, (5.1) где x - собственный вектор. Собственный вектор xi (i=1, …, n), соответствующий собственному значению λ i, является решением однородной системы линейных алгебраических уравнений (A – λ E) x = 0. Пусть матрица A размерности m´ m имеет полную систему нормированных собственных векторов еi (I=1, …, m), т. е. || еi ||=1, и пусть | λ 1| > | λ 2| ³ … ³ | λ m| ³ 0. Зададим вектор
Будем последовательно вычислять векторы по итерационной формуле xn+1 =Axn. Тогда xn можно записать следующим образом:
Представим это равенство в виде xn =c1λ ne1 +o(|λ |n). Тогда имеем (xn, xn)=| c1|2 | λ 1|2n + o(|λ 1|n|λ 2|n). (xn+1, xn)= λ 1| c1|2 | λ 1|2n + o(|λ 1|n|λ 2|n). Находим:
при этом λ В процессе итераций при n e x λ где В случае действительной симметричной матрицы все собственные значения действительны, а отношение Иногда причиной плохой сходимости итераций может быть то, что начальное приближение x(0) оказалось ортогональным собственному вектору, соответствующему максимальному по модулю собственному значению. В этом случае рекомендуется сменить начальное приближение. Для нахождения минимального собственного значения матрицы А, найдем матрицу B= (A - λ 1E) и применим для нее итерационный процесс для нахождения максимального по модулю собственного значения | λ 1(B)|. Если λ 1(A) > 0, то, очевидно, что λ i (B)= λ i (A)- λ 1 (A) ≤ 0, i=1, 2, …, m. Поэтому λ 1(B)= min(λ i(A) - λ 1(A))= min λ i(A) - λ 1(A), то есть minλ i (A)= λ 1(A)+λ 1(B). Если λ 1(A) < 0, то max λ i(A)=min λ i(A)+ λ 1(B). Метод вращения Любую действительную, симметричную матрицу A можно привести к виду A = U ∙ D ∙ U–1 , где U – ортогональная матрица (U –1 = U T ), D – диагональная матрица, где λ i – собственные значения матрицы A. Следовательно, имеем U–1 ∙ A ∙ U = D. На этом свойстве матрицы основан метод вращения: если некоторым ортогональным преобразованием V свести матрицу A к диагональной: Таким образом, нужно построить последовательность ортогональных преобразований, позволяющих неограниченно уменьшать модули недиагональных элементов матрицы A. Обозначим Итак, по заданной матрице A будем строить последовательность Ak так, чтобы Ak-1 находилась через Ak при помощи преобразования подобия со следующей матрицей вращения: Пусть нашли
Строится ортогональная матрица Vn, которая отличается от единичной матрицы E только элементами:
и делается преобразование подобия
При этом матрицы A(n-1) и Vn A(n-1) = B отличаются лишь k –й и l –й строками, т. к. эти матрицы B являются линейными комбинациями тех же строк матрицы A(n-1):
Аналогично k –й и l -й столбцы матрицы A(n):
Элементы являются приближенными к собственным векторам матрицы A. При этом имеет место оценка погрешности
Задания 1. С помощью метода скалярных произведений найти максимальное по модулю и минимальное по модулю собственное значение и соответствующие им собственные вектора для симметричной матрицы A с заданной точностью ε . Провести расчеты при различных начальных приближениях x(0). 2. С помощью метода вращения найти все собственные значения и соответствующие им собственные вектора для симметричной действительной матрицы A с заданной точностью ε . Варианты матриц 1. 3. 5. 7. 9. 11. 13. 15. 17. 19.
Тест: λ 1= -4, 2841, x1 = (-0, 597; -0, 746; 1), λ 2 = 3, 7621, x 2= (1; -0, 492; 0, 423), λ 3 = 5, 522, , x 3= (-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 ||α x||=| α | ||x||, для любого числа А и х ||x+y||≤ ||x||+||y||, для любых x и y Определение. Нормой матрицы А, подчиненной данной норме векторов, называется число Наряду с системой (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 возникает в результате округления. Получим оценку для относительной погрешности решения
Определение. Число ρ (A)= ρ (A)= где λ max, λ min – максимальное и минимальное по модулю собственные значения матрицы A. Матрицы с большим числом обусловленности называются плохо обусловленными. При численном решении систем с такими матрицами возможно сильное накопление погрешности. При небольших изменениях правой части погрешность решения может оказаться значительной. Например, для матрицы число обусловленности ρ (A)= Если взять матрицу и за правую часть системы вектор f= (1, 0000, 0)T, то получим решение
Метод Гаусса Метод Гаусса относится к классу точных методов, т. е. точное решение можно найти за конечное число арифметических операций, в предположении, что нет ошибок округления. В методе Гаусса число арифметических операций равно (2/3)∙ m3. Любую матрицу A можно представить в виде произведения верхнетреугольной V и нижнетреугольной L матриц: A=L∙ V. Если зафиксировать главную диагональ у верхнетреугольной (нижне-треугольной) матрицы, то такое разложение единственно и тогда решение системы можно разбить на два этапа: - нахождение матриц L и V; - решение СЛАУ Ly=f и Vx=y. Метод Гаусса включает прямой ход - исключения неизвестных, и обратный ход - нахождения решения. Рассмотрим решение СЛАУ Ax=f, состоящее из n неизвестных.
Этап I метода Гаусса (прямой ход метода) сводится к преобразованию исходной матрицы к верхнетреугольному виду, используя пошаговое исключение переменных из системы. Шаг 1. Разделим первое уравнение на a11≠ 0, из второго вычитаем первое, умноженное на a21, из третьего вычитаем первое, умноженное на a31, и т. д. Получим На этом 1- й шаг исключения завершен. Далее рассмотрим систему: И аналогичным образом исключим неизвестное x2. Получим систему вида Таким образом, на каждом k -м шаге будем исключать переменную xk (k = 1, 2, …, n-1) по следующему алгоритму: Получим СЛАУ: Обозначим матрицу коэффициентов V=M(n-1)…M(2)M(1)A, вектор правой части g=M(n-1)…M(2)M(1)f. Этап II метода Гаусса (обратный ход метода) состоит в нахождении решения СЛАУ Vx=g из системы с верхнетреугольной матрицей:
Популярное:
|
Последнее изменение этой страницы: 2016-04-10; Просмотров: 1900; Нарушение авторского права страницы