Файл: 10-14.docx

Недостатки методов исключения. Реализация метода Гаусса с сохранением элементарных операций в матрице преобразований.

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

Две системы называются эквивалентными, если все решения первой являются решениями второй и наоборот.

в основе метода Гаусса - элементарные операции:1)перестановка ур-ний местами2)умножение какого-либо ур-ния на число3)замена i-того ур-ния на

сумму i-того и j-того (возможно умноженного на число). Процесс решения системы ур-ний разбивается на 2 этапа:1)прямой ход метода Гаусса2)Обратный ход метода Гаусса. Прямой ход - преобразование системы 1 в систему 2.Обратный ход - решение системы.Недостатки:1)метод не универсален(в процессе прямого хода делим на ведущий элемент, он может оказаться нулём)2)относительно небольшая точность3)в методе нет памяти.

Вычисление обратной матрицы:

A (n*n) A^-1=?

Обратная матрица, если она не вырождена.

AA^-1=A^-1A=E A^-1 =x

AA^-1

A[x]=E

D=1/3n³+1/2n²*n

1/2n²+n³+n²

Операции вычисления обратной матрицы очень трудоёмки.

Ортогональная матрица: QQ^T=Q^TQ=E

[oдействий]

Вычисления определителя матрицы:

detA=S₁+…+S_n

detA= [ 1 a₁₂ … a_1n ] [1 a₁₂ … a_1n ]

a1 [ a₂₁ …… a_2n ] = [0 a₂₂ … a_2n ]

[ a_m1 …… a_mn][0 a_m2 … a_mn]

Два числа взаимообратные (маленьк. и большое), представлена в виде бесконечного произведения (>1_хp₁ (маленьк.)

<1 _хp₂ (больш.)

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

LQ – разложения.

_{-------------- ---------------}

[ ] [\ 0 ] [ ]

[ A ] = [ \ ] [ Q]Это разложение можно получить с помощью матриц:

[ ] [ L \ ] [ ] -- разложения

^{-------------- --------------} -- вращения

Существуют нормализованные разложения

Решение систем ур-ний:

Ax=y

LQx=y 1) Lz=y

2)x=Q^Tz

Предварительно, если нужно вычислить не все строки, а какой-то процент строк!

LQ – вектор строка

Нормализованные разложения каждый раз выбирается строка с максимальной нормой

_________

[\ 0 ]

[ k \ ]

[ \10] [l_kk]<eps~10^-15

^{-----------------------} [l_ii]<[l_ii+1]

L

K – ранг матрицы A

Lu- разложение (на основе метода Гауса)

Любая квадратная матрица А, из которой главные миноры не равны нулю, с помощью невырожденного преобразования может быть преобразована в матрицу u,приэтом матрицаS(преобразования)- нижняя треугольная.

SA=u

S=

U=

Существует нижняя треугольная матрица L, обратная к матрице S, причём L- нижняя треугольная.

LS=SL=E; L=S^-1

Достоинства:

Простота, быстрота, часто применяется

Недостатки:

Такое разложения не существует всегда

QR разложение

Q- ортогональная матрица

R- верхняя треугольная матрица

QQ^T= Q^TQ=E

х= у

Q^TQRX=Q^Tyx= y

Ax=y

QRx=y

R Q^T

x=y D=n^2 + ½ n^2

R

O

P=3/2 n^2

i i

x=

| |

| |

.

y= .

0

i

det A= det(QR)=det Q det R= r11 .. .. .. ..rnn

Независимо от того вырождена матрица или нет есть решения всегда.

На практике часто прибегают решению вырожденой матрицы, для:

Оценка точности, вычисления собственных значений.

Всевозможные аналитическое преобразование.

Определение рагна матрицы.

LQ- разложение

А

0

L

=QЭто разложение можно получиться с помощью:

-разложения

- вращения

Q1Q2Qn-1=

A

Существуют нормальнованные разложения

Решения систем уравнений:

Ax=y1)Lz=y

LQx=y2)x=Q^Tz

Предпочтительно, если нужно вычислять не все строки, а какой то процент строк.

LQ- вектор строка

Нормализованные разложения каждый раз выбирается строка с максимальной нормой

Уточнение собственных значений методом Ньютона.

Lim=0DetA(λi)=0

1. Подставка в матрицу собственных значений и разложение матрицы.

Трацепевидная матрица- собственное значение

Треугольная матрица- не решается

2. hz=d\dxA(λi)qn- последняя строка ортогональной матрицы (собственый вектор)

[d\dxA(λi)=A1, еслизадачаA1λ+A0]

3. Ньютоновская поправка

λi+1=λi- 1/Z(n) -оценка точности,

-уточнение собственных

значений (если необходимо)

-собственный вектор

A(λi)=LQ^T

Ортогональные матрицы вращения (преобразования Гивенса), их использование для реализации QR-разложения.

Пусть iи j— некоторые целые индексы, такие что l ≤ i<j ≤ n,aθ — некоторое вещественное число. Рассмотрим следующую матри­цу размерностиn:

(такая матрица отличается отединичной лишь тем, что на пересече­ниях ее (i, j) строк и столбцов расставлены величины cosθ и sinθ).

Проверкой условия: если определяющая линейный оператор матрица Q удовлетворяет соотноше­нию Q^TQ = Е = I, (то есть ее обратная матрица совпадает с транспонированной)легко можно убедиться, что определяемый матрицей оператор является ортогональным.

Пусть имеется некоторый вектор х Rⁿ и его образ х' = х. Очевидно, что они отличаются лишь i-ым и j-ым компонентами, для которых справедливо соотношение

(1)

На практике обычно возникает задача нахождения такого враще­ния, которое обнуляло бы один из компонентов х_i, или . Обозна­чим для краткости с = cosθи s = sinθ. Если требуется обнулить x_j, то согласно (1) нужно найти такие c и s, чтобы выполнялось cx_j — sx_i = 0. Добавив к этому уравнению связывающее c и s основное тригонометрическое тождество, получим систему из двух уравнений с двумя неизвестными:

имеющую решение

Для хранения матриц вращения достаточно двух це­лых (i, j) и двух вещественных (s, с) чисел; процедура матрично-векторного умножения при этом выполняется согласно формулам (1).

Свойства:

• произведение ортогональных матриц также является ортогональной матрицей;

• матрица, обратная к ортогональной, также ортогональна.

• (Q₁Q₂)Q₂^-1Q₁^-1 = E

• Q₁Q₂ · Q₂^TQ₁^T = E

• (Q₁Q₂)(Q₁Q₂)^T = E

Замечание: чем больше , тем точнее результат деления, тем точнее оценка матрицы

Если cosθ=1 и sinθ=0, то ортогональная матрица становится единичной.

Трудоемкость метода = kn³, где k<1 (зависит от конкретной реализации ≈ n³)

Метод Гивенса основан на преобразовании подобия. Алго­ритм построен таким образом, что вновь образованные нулевые элементы при всех последующих преобразованиях сохраняются. Его единственный недоста­ток состоит в том, что симметричная матрица приводится не к диагональному, а к трехдиагональному виду.

В случае матрицы размерности п х п метод Гивенса требует п — 2 основных шагов, на каждом из которых выполняется ряд преобразований, число которых зависит от числа нулей, кото­рое хотят получить в данном столбце или строке. На k -м шаге обращают в нули элементы, стоящие вне трех диагоналей k-й строки и k -го столбца, сохраняя в то же время нулевые элементы, полученные на предыдущих шагах. Таким образом, перед нача­лом k -го шага преобразованная матрица является трехдиа­гональной, если ограничиться рассмотрением ее первых k — 1 строк и столбцов. По мере преобразований симметричная матри­ца размерности 5х5 приобретает следующие формы:

На каждом основном шаге изменяются лишь те элементы мат­рицы а_ij, которые расположены в ее правой нижней (заштрихо­ванной) части. Ясно, что на каждой следующей стадии вы­полняется меньшее число преобразований, чем на предыдущей. Всего для приведения матрицы к трехдиагональному виду тре­буется выполнить (n² —Зп + 2)/2 преобразований.

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

Решение частичной проблемы собственных значений. Степенной метод и его модификации.

Решение частичной проблемы собственных значений сводится к поиску нескольких собственных значений (наибольших, наименьших)

При степенном методе определяется одно наибольшее собственное значение

Степенной метод

А – λЕ

λ₁, … λ_n – собственные значения

- для i-того элемента

Рассмотрим отношение:

так как │λ₁│это max значение, то с ростом k вес значения в скобках будет стремиться к нулю, поэтому через определенное число итераций получим

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

Оценка погрешности:

Если матрица плохо обусловленная, то погрешность задания ее коэффициентов сильно влияет на результат

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