Учебник - Практические занятия по вычислительной математике - Аристова, страница 7

LU-разложениеСреди прямых методов численного решения СЛАУ широко используется также LU-разложение матрицы А, эквивалентное методу Гаусса, иметод Холецкого (или метод квадратного корня).Если матрица А представима в виде произведений матриц LU, тоСЛАУ может быть представлена в виде (LU)u = f.Перепишем исходную систему, вводя вспомогательный вектор v, вследующем виде:Lv = f, Uu = v.Решение СЛАУ свелось к последовательному решению двух систем стреугольными матрицами.

Первый этап решения системы Lv = f:v1  f1 ,l21v1  v2  f 2 ,ln1v1  ln 2 v2  ln,n 1vn 1  vn  f n ,откуда можно вычислить все vk последовательно по формуламk 1vk  f k   lkj v j ; k  2,,n.j 1Далее, рассмотрим систему Uu = v илиd11u1  d 2u2   d1n un  v1 ,d 22u2   d 2 n un  v2 ,.d nn un  vn ,39II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫрешение которой находятся в обратном порядке, т.е. при k = n – 1,…,1 по1очевидным формулам uk  d kk(vk nj  k 1d kj u j ).Условия существования такого разложения даются следующей теоремой.Теорема 2. Если все главные миноры квадратной матрицы А отличны от нуля, то существуют единственные нижняя и верхняя треугольные матрицы L = {lij} и U = {dij} такие, что А = LU.

При этом вседиагональные коэффициенты матрицы L фиксированы и равны единице.II.4.3. Метод Холецкого (метод квадратного корня)ПустьматрицарассматриваемойлинейнойсистемыА – симметричная, т.е. aij = aji, положительная матрица. Тогда она представима в виде А = LLT, гдеl1n 0  l11 l12 l11 0ll00ll222n .LT  , L   12 220lnn lnn 0 l1n l2nДалее, как и в случае LU-разложения, решение СЛАУ Аu = f сводится к последовательному решению двух линейных систем с треугольнымиматрицами Lv = f, LTu = v, для решения которых требуется примерно 2n2арифметических действий.Первая из этих линейных системl11v1  f1,l12v1  l22v2  f 2 ,…l1n v1  l2n v2   lnnvn  f n ,она легко решается. Для решения получаем очевидные формулыivi  lii1 ( fi   lki vk ), i = 1,…, n.k 1Вторая система уравнений естьl11u1  l12u2   l1nun  v1,l22u2   l2nun  v2 ,…lnnun  vn .40II.5.

Итерационные методы решения СЛАУИз нее находим значения переменных ui в обратном порядке по формуламuk  lii1 (vk nj  k 1lk j u j ).Определенной опасностью при реализации этого метода являютсявозможная близость к нулю lii и отрицательность подкоренных выражений при вычислении lii (последнего не должно быть при симметричнойположительной матрице А).II.5. Итерационные методы решения СЛАУII.5.1. Метод простой итерацииРассмотрим систему линейных алгебраических уравнений Au = f.Проведем несколько равносильных преобразований.

Умножим обечасти системы на один и тот же скалярный множитель τ, затем прибавим кправой и левой частям системы вектор u. Систему уравнений можно теперь записать в виде, удобном для итерацийu = Ru + F,где R = E – τA, F = τf. R называется матрицей перехода.Теперь построим последовательность приближений к решению системы. Выберем произвольный вектор u(0) – начальное приближение крешению. Чаще всего его просто полагают нулевым вектором. Скореевсего, начальное приближение не удовлетворяет исходной системе. Приподстановке его в исходное уравнение возникает невязка r(0) = f – Au(0).Вычислив невязку, можно уточнить приближение к решению, считая чтоu(1) = u(0) + τr (0).По первому приближению снова вычисляется невязка, процесс продолжается.

В ходе итерации получаем u(k+1) = u(k) + τr(k), r(k) = f – Au(k). Эквивалентная формулировка метода, называемого методом простых итераций, заключается в следующем. Решение системы Au = f находится какпредел последовательности {u(0), u(1), u(2), …} приближений, члены которой связаны рекуррентным соотношениемu(k + 1) = Ru(k) + F,u(0) = 0 (или любому произвольному вектору). Если предел такой последовательности существует, то говорят о сходимости итерационного процесса к решению СЛАУ.Существуют другие формы записи метода итераций, например41II.

ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫu(k 1)  (E  A)u(k )  f .Теорема 3. (Достаточное условие сходимости метода простой итерации). Итерационный процесс u(k+1) = Ru(k) + F, сходится к решению UСЛАУ Au = F со скоростью геометрической прогрессии при выполненииусловия: ||R|| ≤ q < 1.Доказательство . Пусть U – точное решение системы. Вычитая източного равенства AU = f равенство u(k+1) = Ru(k) + F, получим u(k) –U = R(u(k –1) – U).

Обозначив погрешность ε(k) = u(k) – U, получим для эволюции погрешности уравнение ε(k) = Rε(k–1).Справедлива цепочка неравенств:u( k )  U  ε(k ) R  ε(k 1)  q ε(k 1)  q k ε(0)  q k u(0)  U ,где 0 < q ≤||R||. Отсюда следует, что при q < 1 lim u(k )  U. ■kИз неравенства ||ε(k) || ≤ qk||ε(0)|| можно получить оценку количестваитераций, необходимых для достижения точности ε, т.е. для выполнения условия ||u(k) – U|| = ||ε(k)|| ≤ ε Эта оценка имеет вид k   ln / ln q. || 0 || Теорема 4.

(Критерий сходимости метода простой итерации).Пусть СЛАУ имеет единственное решение. Тогда для сходимости итерационного процесса u(k+1) = Ru(k) + F необходимо и достаточно, чтобывсе собственные значения матрицы R по абсолютной величине былименьше единицы.II.5.2. Каноническая форма записи двухслойных итерационныхметодовКанонической формой записи двухслойного итерационного процесса называется следующая:Bk 1u(k 1)  u(k ) Au(k )  f .k 1При Bk = E, τk = τ последняя формула соответствует однопараметрическому итерационному процессу – рассмотренному выше методу простых итераций.

При Bk = E, τk = {τk, k = 1, …, n} – n-шаговому явномуитерационному процессу, при Bk = B', τk = 1 – методу простой итерациибез итерационного параметра. В случае, когда B ≠ E, итерационный метод42II.5.3. Методы Якоби, Зейделя, верхней релаксацииназывается неявным – для вычисления следующего приближения к решению придется решать (как правило, более простую, чем исходную) систему линейных уравнений.II.5.3. Методы Якоби, Зейделя, верхней релаксацииПредставим матрицу А в видеА = L + D + U,где L и U – нижняя и верхняя треугольные матрицы с нулевыми элементами на главной диагонали, D – диагональная матрица. РассматриваемаяСЛАУ может быть переписана в следующем эквивалентном виде:Lu + Du + Uu = f.Построим два итерационных процессаLu(k) + Du(k+1)+ Uu(k) = fиLu(k+1)+ Du(k+1)+ Uu(k) = f,или, соответственно,u(k+1) = –D–1(L+U)u(k) + D–1fиu(k+1) = –(L+D)–1Uu(k) + (L+D)–1f.Очевидно, что эти формулы описывают итерационные методы видаu(k+1) = Ru(k) + F, если положить в первом случаеR = –D–1(L+U), F = D–1fилиR = –(L+D)–1U, F = (L+D)–1fво втором.Эти итерационные методы называются методами Якоби и Зейделясоответственно.Теорема 5 .

(Достаточное условие сходимости метода Якоби).Итерационный метод Якоби сходится к решению соответствующейСЛАУ, если выполнено условие диагонального преобладания43II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫaii nj 1, j iaij , i = 1,…,n.Теорема 6. (Критерий сходимости итерационного метода Якоби).Для сходимости итерационного метода Якоби необходимо и достаточно, чтобы все корни уравненияa11 a12a21 a22a1na2nan1annan 20по модулю не превосходили единицы.Теорема 7. (Критерий сходимости итерационного метода Зейделя).Для сходимости итерационного метода метода Зейделя необходимо идостаточно, чтобы все корни уравненияa11 a12a21 a22a1na2nan1annan 20по модулю не превосходили единицы.Теорема 8. (Достаточное условие сходимости метода Зейделя).Пусть А – вещественная, симметричная, положительно определеннаяматрица.

В этом случае итерационный метод Зейделя сходится.Развитием метода Зейделя является метод релаксации. В предположении, что метод Зейделя меняет вектор решения в правильном направлении, хочется пройти по этому пути несколько дальше:ui(k 1)  ui(k )   zi(k 1)  ui(k ) ,(k )где zi – i-я компонента решения, полученная методом Зейделя. В этомметоде введен параметр релаксации ω. Метод релаксации может бытьпредставлен в матричной форме(Lu(k 1)  Du(k 1) )  ( 1)Du(k )  Uu(k )  f .44II.6. О спектральных задачахВыбором ω можно существенно изменять скорость сходимости итерационного метода.Выразим u(k+1)u( k 1)  (D  L)1 ( 1)D  L u( k )  (D  L)1 f .В общем случае задача вычисления ωопт (оптимального итерационного параметра) не решена, однако известно, что 1 < ωопт < 2.

В этом случаеитерационный метод называется методом последовательной верхней релаксации или SОR – Successive over relaxation. Иногда встречается термин«сверхрелаксация» при 1 < ωопт < 2. При 0 < ω < 1 имеем метод нижнейрелаксации.Для очень важного частного случая, когда существует перестановкапеременных P, такая что матрица A после перестановки имеет вид T:T12 DT  PAPT   1, T21 D2 где D1, D2 – диагональные матрицы, оптимальное значение релаксационного параметра можно определить через спектральный радиус матрицыперехода метода Якоби ρ(RJ), RJ =D–1(L + U)2опт .1  1  2 ( R J )Условие существование перестановки P означает, что вектор переменныхраспадается на два класса, так что каждая компонента вектора из одногокласса зависит только от компонент из другого класса.II.6.

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

Выбираем произвольный ненулевой вектор u(0)и строим последовательность векторовu(k+1) = Au(k).45II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫЛегко показать, что выражение( Au( k ) , u( k ) ) (u( k 1) , u( k ) )(u(k ) , u(k ) )(u(k ) , u(k ) )приближает максимальное по абсолютной величине собственное значениес точностью O(λN / λN –1)k.

Здесь λN / λN –1 – отношение самого большого помодулю собственного числа матрицы к следующему по абсолютной величине.Для решения полной самосопряженной проблемы собственных значений применяется метод вращений.Определение собственных значений самосопряженной матрицы Aэквивалентно отысканию такой ортогональной матрицы T, чтоΛ = T'AT,матрица Λ – диагональная.Среди всех ортогональных преобразований данное минимизируетсумму квадратов внедиагональных элементов исходной матрицы. Построим итерационный метод, минимизирующий эту сумму на каждойитерации. Пусть каждое преобразование подобия на каждой итерацииˆ  T AT , где матрица Tij естьсодержит лишь одну матрицу вращения Aijijматрица поворота в плоскости (ui, uj) на угол α.