1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

е. Ax̃ − b.ОпределениеДля системы линейных алгебраических уравнений Ax = b неязкаприближённого решения x̃ — это вектор разности левой и правойчастей системы после подстановки в него x̃, т. е. Ax̃ − b.Применение принципа релаксации может заключаться в том, чтона каждом шаге итерационного процесса стремятся уменьшитьмодули компонент вектора невязки либо её норму, либо какую-тозависящую от них величину.Методы Якоби и Гаусса-Зейделя можно рассматривать какитерационные процессы, в которых также осуществляетсярелаксация, поскольку на каждом их шаге компоненты очередногоприближения вычисляются из условия зануления соответствующихкомпонент невязки.Итерационные методы релаксациидля решения систем линейных уравненийРазличают релаксацию полную и неполную,в зависимости от того, добиваемся ли мы на каждом отдельномшаге итерационного процесса (или его подшаге) наибольшеговозможного улучшения рассматриваемой функции от погрешностиили нет.Локально полная релаксация может казаться наиболее выгоднойна одной итерации.Но глобально, с точки зрения сходимости процесса в целом,тщательно подобранная неполная релаксация нередко приводит кболее эффективным методам.Популярной реализацией высказанных общих идей являетсяитерационный метод решения систем линейных алгебраическихуравнений, в котором для улучшения сходимости берётся«взвешенное среднее» значений компонент предшествующей x(k) ипоследующей x(k+1) итераций метода Гаусса-Зейделя.Популярной реализацией высказанных общих идей являетсяитерационный метод решения систем линейных алгебраическихуравнений, в котором для улучшения сходимости берётся«взвешенное среднее» значений компонент предшествующей x(k) ипоследующей x(k+1) итераций метода Гаусса-Зейделя.Более точно, зададимся вещественным числом ω,которое будем называть параметром релаксации.Тогда i-ую компоненту очередного (k + 1)-го приближения положимравной(k+1)ωxi(k)+ (1 − ω)xi ,(k)где xi — i-ая компонента приближения, полученного в результате(k+1)k-го шага алгоритма, а xi— i-ая компонента приближения,(k+1)(k+1)(k)которое было бы получено на основе x(k) и x1, .

. . , xi−1 , xi+1 ,(k). . . , xn с помощью метода Гаусса-Зейделя.Метод релаксации для решения систем линейных уравненийk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )DO FOR i = 1 TO n(k+1)xi(k)← (1 − ω) xi+END DOk ← k + 1;END DOω bi −aiii−1Xj=1(k+1)aij xj−nXj=i+1(k)aij xj Расчётные формулы этого метода перепишем в виде(k+1)aii xi+ωi−1Xj=1(k+1)aij xj(k)= (1 − ω) aii xi−ωnX(k)aij xj + ωbi ,j=i+1i = 1, 2, . . . , n,k = 0, 1, 2, . .

. .Расчётные формулы этого метода перепишем в виде(k+1)aii xi+ωi−1Xj=1(k+1)aij xj(k)= (1 − ω) aii xi−ωnX(k)aij xj + ωbi ,j=i+1i = 1, 2, . . . , n,k = 0, 1, 2, . . . .Используя введённые ранее матрицы L̃, D и Ũ ,можно придать этим соотношениям более компактный вид.Пусть A = L̃ + D + Ũ , где0 a210...L̃ =  a31 a32 ... ......0an1 an2 · · · an,n−1 00— диагональ матрицы A,D = diag {a11 , a22 , . . . , ann }Ũ = 0 a12 · · · a1,n−1...

a2,n−10......00— строго нижняятреугольная матрица,a1nan−1,n0a2n...— строго верхняятреугольная матрица.Тогда формулам(k+1)aii xi+ωi−1X(k+1)aij xj(k)= (1 − ω) aii xi−ωnX(k)aij xj + ωbi ,j=i+1j=1i = 1, 2, . . . , n,можно придать видD + ω L̃ x(k+1) = (1 − ω)D − ω Ũ x(k) + ωb.Окончательноx(k+1) = D + ω L̃−1−1(1 − ω)D − ω Ũ x(k) + D + ω L̃ ωb,k = 0, 1, 2, . . . .В зависимости от конкретного значения параметра релаксациипринято различать три случая:если ω < 1, то говорят о «нижней релаксации»,если ω = 1, то имеем итерации Гаусса-Зейделя,если ω > 1, то говорят о «верхней релаксации».В англоязычной литературе по вычислительной линейной алгебреэтот метод обычно обозначают аббревиатуройSOR(ω).Она происходит от термина «Successive OverRelaxation»— «последовательная перерелаксация».Последний случай может показаться экзотичным, но во многихситуациях он действительно обеспечивает улучшение сходимостиитераций в сравнении с методом Гаусса-Зейделя.Несколько упрощённое объяснение этого явления может состоятьв следующем:Если направление от x(k) к x(k+1) оказывается удачным в томсмысле, что приближает к искомому решению, то имеет смыслпройти по нему и дальше, за x(k+1) .Это соответствует случаю ω > 1.Последний случай может показаться экзотичным, но во многихситуациях он действительно обеспечивает улучшение сходимостиитераций в сравнении с методом Гаусса-Зейделя.Несколько упрощённое объяснение этого явления может состоятьв следующем:Если направление от x(k) к x(k+1) оказывается удачным в томсмысле, что приближает к искомому решению, то имеет смыслпройти по нему и дальше, за x(k+1) .Это соответствует случаю ω > 1.Методы релаксации развиты Д.

Янгом в середине XX века.Метод релаксации также укладывается в схему итерационныхпроцессов, порождаемых расщеплением матрицы системы.Именно, мы берём A = Gω − Hω с матрицамиGω = D + ω L̃,Hω = (1 − ω)D − ω Ũ .Необходимое и достаточное условие сходимости метода релаксациипринимает поэтому видρ G−1ω Hω < 1.Метод релаксации также укладывается в схему итерационныхпроцессов, порождаемых расщеплением матрицы системы.Именно, мы берём A = Gω − Hω с матрицамиGω = D + ω L̃,Hω = (1 − ω)D − ω Ũ .Необходимое и достаточное условие сходимости метода релаксациипринимает поэтому видρ G−1ω Hω < 1.Для некоторых специфичных, но очень важных задач значениерелаксационного параметра ω, при котором величина ρ G−1ω Hωдостигает минимума, находится относительно просто.В более сложных задачах для оптимизации ω требуется весьматрудный анализ спектра матрицы перехода G−1ω Hω .Лемма КаханаПусть в методе релаксации с параметром ω матрицей оператораперехода является−1Cω = D + ω L̃(1 − ω)D − ω Ũ .Тогдаρ(Cω ) ≥ |ω − 1|,и, как следствие, для сходимости метода релаксации из любогоначального приближения необходимо, чтобы выполнялосьнеравенство 0 < ω < 2.William Kahan (1933 – )Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П.

ШарыйКафедра математического моделирования НГУЛекция 20 декабря 2017 г.Итерационные методы релаксациидля решения систем линейных уравненийПусть задано вещественное число ω,которое будем называть параметром релаксации.Тогда i-ую компоненту очередного (k + 1)-го приближения положимравной(k+1)ωxi(k)+ (1 − ω)xi ,где(k)xi — i-ая компонента приближения, полученного в результатепредшествующего k-го шага алгоритма,(k+1)xi— i-ая компонента приближения, которое было бы(k+1)(k+1)(k)(k)получено на основе x(k) и x1, . .

. , xi−1 , xi+1 , . . . , xnс помощью метода Гаусса-Зейделя.Метод релаксации для решения систем линейных уравненийk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )DO FOR i = 1 TO n(k+1)xi(k)← (1 − ω) xi+END DOk ← k + 1;END DOω bi −aiii−1Xj=1(k+1)aij xj−nXj=i+1(k)aij xj Пусть A = L̃ + D + Ũ , где0 a210...L̃ =  a31 a32 ... ......0an1 an2 · · · an,n−1 00— диагональ матрицы A,D = diag {a11 , a22 , . .

. , ann }Ũ = 0 a12 · · · a1,n−1... a2,n−10......00— строго нижняятреугольная матрица,a1nan−1,n0a2n...— строго верхняятреугольная матрица.Расчётные формулы метода релаксации можно переписать вматрично-векторном виде:x(k+1) = D + ω L̃−1−1(1 − ω)D − ω Ũ x(k) + D + ω L̃ ωb,k = 0, 1, 2, . . . .Необходимое и достаточное условие сходимости метода релаксации−1ρ D + ω L̃(1 − ω)D − ω Ũ < 1.Лемма КаханаПусть в методе релаксации с параметром ω матрицей оператораперехода является−1Cω = D + ω L̃(1 − ω)D − ω Ũ .Тогдаρ(Cω ) ≥ |ω − 1|,и, как следствие, для сходимости метода релаксации из любогоначального приближения необходимо, чтобы выполнялосьнеравенство 0 < ω < 2.William Kahan (1933 – )Доказательство:Прежде всего, преобразуем матрицу Cω для придания ей болееудобного для дальнейших выкладок вида:Cω ====D + ω L̃−1(1 − ω)D − ω Ũ−1D(I + ωD −1 L̃)(1 − ω)D − ω Ũ−1I + ωD −1 L̃ D −1 (1 − ω)D − ω Ũ−1I + ωD −1 L̃(1 − ω)I − ωD −1 Ũ .Желая исследовать расположение собственных чисел λi (Cω )матрицы Cω , рассмотрим её характеристический полиномφ(λ) = det(Cω − λI)= detI + ωD −1 L̃−1(1 − ω)I − ωD −1 Ũ − λI= pn λn + pn−1 λn−1 + .

. . + p1 λ + p0 ,в котором pn = (−1)n по построению.Свободный член p0 характеристического полинома может бытьнайден как φ(0):p0 = det Cω = detI + ωD −1 L̃−1(1 − ω)I − ωD −1 Ũ= det (I + ωD −1 L̃)−1 · det (1 − ω)I − ωD −1 Ũ= det (1 − ω)I − ωD −1 Ũ= (1 − ω)n ,так какматрица (I + ωD −1 L̃) — нижняя треугольнаяc диагональными элементами имеет единицы,(1 − ω)I − ωD −1 Ũ — верхняя треугольная,с элементами (1 − ω) по главной диагонали.НапомнимТеорема Виета (частный случай)Свободный член полинома n-ой степени, делённый на старшийкоэффициент, равен произведению всех корней полинома,умноженному на (−1)n .НапомнимТеорема Виета (частный случай)Свободный член полинома n-ой степени, делённый на старшийкоэффициент, равен произведению всех корней полинома,умноженному на (−1)n .Следствие.Свободный член характеристического полинома матрицы,делённый на старший коэффициент, равен произведению его корней— собственных чисел матрицы, — умноженному на (−1)n .ПоэтомуnYi=1λi (Cω ) = (1 − ω)n .ПоэтомуnYλi (Cω ) = (1 − ω)n .i=1Отсюда необходимо следуетmax |λi (Cω )| ≥ |ω − 1|.1≤i≤nЭто доказывает лемму Кахана.Итерационные методы релаксациидля решения систем линейных уравненийТеорема Островского-РайхаЕсли в системе линейных алгебраических уравнений Ax = bматрица A является симметричной положительно определённой,то для всех значений параметра ω ∈ ]0, 2[ метод релаксациисходится к решению из любого начального приближения.Ostrowski–Reich theoremИтерационные методы релаксациидля решения систем линейных уравненийТеорема Островского-РайхаЕсли в системе линейных алгебраических уравнений Ax = bматрица A является симметричной положительно определённой,то для всех значений параметра ω ∈ ]0, 2[ метод релаксациисходится к решению из любого начального приближения.Ostrowski–Reich theoremДоказательство опускается.Читатель может найти егов продвинутых книгах по вычислительной линейной алгебре.Нестационарные итерационные методыдля решения систем линейных уравненийВ основу нестационарных итерационных методовмогут быть положены различные идеи.Нестационарные итерационные методыдля решения систем линейных уравненийВ основу нестационарных итерационных методовмогут быть положены различные идеи.В качестве первого примера рассмотрим метод простой итерацииx(k+1) ← (I − τ A) x(k) + τ b,k = 0, 1, 2, .

. . .Нестационарные итерационные методыдля решения систем линейных уравненийВ основу нестационарных итерационных методовмогут быть положены различные идеи.В качестве первого примера рассмотрим метод простой итерацииx(k+1) ← (I − τ A) x(k) + τ b,k = 0, 1, 2, . . . .Если переписать его в видеx(k+1) ← x(k) − τ Ax(k) − b ,k = 0, 1, 2, . . . ,то расчёт каждой последующей итерации x(k+1) можеттрактоваться как вычитание из x(k) поправки, пропорциональнойвектору текущей невязки (Ax(k) − b).Но при таком взгляде на итерационный процесс можно изменятьпараметр τ в зависимости от шага, т. е.

Характеристики

Список файлов лекций