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

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

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

. .0Таким образом, −1D (L̃ + Ũ )откуда следует доказываемое.∞< 1,Итерационный метод Якоби— был изобретён в середине XIX века и сейчас при практическомрешении систем линейных уравнений используется редко.Он существенно проигрывает по эффективностиболее современным численным методам.Итерационный метод Якоби— был изобретён в середине XIX века и сейчас при практическомрешении систем линейных уравнений используется редко.Он существенно проигрывает по эффективностиболее современным численным методам.Тем не менее, совсем забывать метод Якобибыло бы преждевременным.Лежащая в его основе идея выделения из оператора системыуравнений «диагональной части» достаточно плодотворнаи может быть с успехом применена в различных ситуациях.Обобщения метода ЯкобиРассмотрим систему уравненийAx = b(x),в которойA = (aij ) — n × n-матрица,x = ( x1 , x2 , .

. . , xn )⊤ — вектор неизвестных,⊤b(x) = b1 (x), b2 , . . . , bn (x) — вектор-функция от неизвестных x.Если b(x) — нелинейная функция, то численные методыдля решения систем линейных уравнений уже неприменимы.Но для отыскания решения мы можем воспользоватьсянезначительной модификацией итераций ЯкобиX1 (k+1)(k)xi←bi x(k) −aij xj  ,i = 1, 2, . .

. , n,aiij6=ik = 0, 1, 2, . . . , с некоторым начальным приближением x(0) .Но для отыскания решения мы можем воспользоватьсянезначительной модификацией итераций ЯкобиX1 (k+1)(k)xi←bi x(k) −aij xj  ,i = 1, 2, . . . , n,aiij6=ik = 0, 1, 2, . . . , с некоторым начальным приближением x(0) .Если b(x) изменяется «достаточно медленно», так что ′ bi (x)/aii < 1для любых x ∈ Rn при всех i = 1, 2, . . . , n, то выписанныйитерационый метод сходится для произвольного начальногоприближения.Это следует, к примеру, из теоремы Шрёдера о неподвижной точке.Вообще, можно определить нелинейный итерационныйметод Якоби в применении к системе уравненийF1 ( x1 , x2 , . . .

, xn ) = 0, F2 ( x1 , x2 , . . . , xn ) = 0,.........Fn ( x1 , x2 , . . . , xn ) = 0.Задавшись каким-то начальным приближением x(0) , на очередномk-ом шаге последовательно находят решения x̃i уравнений(k)(k)(k)Fi x1 , . . . , xi−1 , xi , xi+1 , . . . , x(k)= 0,n(k+1)относительно xi , а затем полагают xii = 1, 2, . . . , n← x̃i , i = 1, 2, . . . , n.Итерационный метод Гаусса-ЗейделяВ итерационном методе Якоби при вычислениях по инструкции(k+1)xi1←aiibi −X(k)aij xjj6=i!,i = 1, 2, .

. . , n,компоненты очередного приближения x(k+1)находятся последовательно одна за другой.(k+1)Поэтому к моменту вычисления xi(k+1)уже известны x1(k+1), x2(k+1), . . . , xi−1 .Но метод Якоби никак не использует эти новые значения, и привычислении любой компоненты следующего приближения всегдаопирается только на вектор x(k) предшествующего приближения.Но метод Якоби никак не использует эти новые значения, и привычислении любой компоненты следующего приближения всегдаопирается только на вектор x(k) предшествующего приближения.Если итерации сходятся к решению, то естественно ожидать, чтовсе компоненты x(k+1) ближе к искомому решению, чем x(k) .Поэтому немедленное вовлечение их в процесс вычислений будетспособствовать ускорению сходимости.На этой идее основан итерационный метод Гаусса-Зейделя,псевдокод которого представлен в Таблице далее.Итерационный метод Гаусса-Зейделяk ← 0;выбираем начальное приближение x(0) ;DO WHILE ( метод не сошёлся )DO FOR i = 1 TO nni−1XX1(k)(k+1)(k+1) bi −aij xj xi←aij xj−aiij=1j=i+1END DOk ← k + 1;END DOk — счётчик итерацийВ методе Гаусса-Зейделя суммирование в формуле для вычисленияi-ой компоненты очередного приближения x(k+1) разбито на двечасти —по индексам, предшествующим i,по индексам, следующим за i.Первая часть суммы использует новые вычисленные значения(k+1)(k+1)(k)(k)x1, .

. . , xi−1 , а вторая — компоненты xi+1 , . . . , xn из старогоприближения.В методе Гаусса-Зейделя суммирование в формуле для вычисленияi-ой компоненты очередного приближения x(k+1) разбито на двечасти —по индексам, предшествующим i,по индексам, следующим за i.Первая часть суммы использует новые вычисленные значения(k+1)(k+1)(k)(k)x1, . . . , xi−1 , а вторая — компоненты xi+1 , . . . , xn из старогоприближения.Метод Гаусса-Зейделя иногда называют также итерационнымметодом «последовательных смещений».Его основная идея — немедленно вовлекать уже полученнуюинформацию в вычислительный процесс — с успехом применима идля нелинейных итерационных схем.Пусть 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−1Xj=1(k+1)aij xj=−nXj=i+1(k)aij xj + bi ,i = 1, 2, . . . , n.Чтобы получить для метода Гаусса-Зейделя матричноепредставление, перепишем его расчётные формулы в виде(k+1)aii xi+i−1Xj=1(k+1)aij xj=−nX(k)aij xj + bi ,i = 1, 2, .

. . , n.j=i+1Используя матрицы L̃, D и Ũ , на которые разлагается A, можемзаписать эти формулы в виде(D + L̃) x(k+1) = −Ũx(k) + b,т. е.x(k+1) = −(D + L̃)−1 Ũ x(k) + (D + L̃)−1 b,k = 0, 1, 2, . . . .Таким образом, метод Гаусса-Зейделя можно рассматривать какитерационный метод, порождённый таким расщеплением матрицыСЛАУ в виде A = G − H, чтоG = D + L̃,H = −Ũ .В силу Теоремы о сходимости стационарных одношаговыхитерационных процессов необходимым и достаточным условиемсходимости метода Гаусса-Зейделя из любого начальногоприближения является неравенствоρ (D + L̃)−1 Ũ < 1.Как и в случае аналогичного условия для метода Якоби,оно имеет, главным образом, теоретическое значение.Итерационный метод Гаусса-ЗейделяТеоремаЕсли в системе линейных алгебраических уравнений Ax = bматрица A — квадратная и имеет диагональное преобладание, тоитерационный метод Гаусса-Зейделя для решения этой системысходится при любом начальном приближении.Доказательство.Если матрица A имеет диагональное преобладание,то она неособенна (признак неособенности Адамара).Как следствие, решение x⋆ линейной системы Ax = bтогда существует и единственно.Доказательство.Если матрица A имеет диагональное преобладание,то она неособенна (признак неособенности Адамара).Как следствие, решение x⋆ линейной системы Ax = bтогда существует и единственно.Пусть x(k) — приближение к решению,полученное на k-ом шаге итерационного процесса.Исследуем поведение погрешности решенияz (k) := x(k) − x⋆ ,в зависимости от номера итерации k.Чтобы получить формулу для z (k) , предварительно перепишемсоотношения, которым удовлетворяет точное решение x⋆ .Вместо исходных уравнений системыnXaij x⋆j = bi ,i = 1, 2, .

. . , n.j=1можно придать им следующий эквивалентный вид1x⋆i =aiibi −i−1Xj=1aij x⋆j −nXj=i+1!aij x⋆j ,i = 1, 2, . . . , n.Вычтем почленно найденные равенстваиз расчётных формул метода Гаусса-Зейделя, т. е. из(k+1)xi1=aiibi −i−1X(k+1)aij xj−nX(k)aij xjj=i+1j=1!,i = 1, 2, . . . , n.Мы получим(k+1)zi1=aii−i−1Xj=1(k+1)aij zj−nXj=i+1(k)aij zj!,i = 1, 2, . . . , n.Возьмём абсолютные значения от обеих частей этих равенств,воспользуемся неравенством треугольника для оценки суммв правых частях: ni−1 XX aij (k) aij (k+1) (k+1) · z + · z ≤zji aii j aii j=i+1j=1 ni−1 (k+1) X (k) X aij aij ≤ z aii aii + z∞∞j=1для i = 1, 2, . . . , n.j=i+1(1)Условие диагонального преобладания в матрице A, т. е.X|aij | < |aii |,i = 1, 2, . .

. , n,j6=iозначает существование константы κ, 0 ≤ κ < 1, такой чтоX|aij | ≤ κ |aii |,i = 1, 2, . . . , n.j6=iУсловие диагонального преобладания в матрице A, т. е.X|aij | < |aii |,i = 1, 2, . . . , n,j6=iозначает существование константы κ, 0 ≤ κ < 1, такой чтоX|aij | ≤ κ |aii |,i = 1, 2, . . . , n.j6=iПо этой причинеX aij ≤ κ, aii i = 1, 2, . . .

, n,j6=iоткуда следует!n i−1 i−1 i−1 XXXX aij aij aij aij ≤ κ−κ = κ 1− . ≤ κ− aii aii aii aii j=i+1j=1j=1j=1Подставляя полученную оценку в неравенства (1), приходим ксоотношениям!i−1 i−1 X aij (k+1) X (k+1) aij (k) + κz ≤ zz ,1−i aii aii ∞∞j=1(2)j=1i = 1, 2, . . . , n. (k+1) достигается при i = l, так чтоПредположим, что max1≤i≤n zi (k+1) z∞ (k+1) .= zlРассмотрим теперь отдельно l-ое неравенство из (2).(3)Привлекая равенство (3), можем утверждать, что (k+1) zто есть∞!l−1 l−1 X alj (k+1) X alj (k) , + κz ≤ z1−a a ∞∞ (k+1) zj=1∞llj=1ll!!l−1 l−1 XX (k) alj alj .

≤ κz 1−1− all all ∞j=1j=1(4) (k+1) z∞!!l−1 l−1 XX alj alj (k) ≤ κz .1−1−a a ∞j=1llj=1llДалее, в силу диагонального преобладания в матрице A1−l−1 X alj > 0,a j=1llи на эту величину можно сократить обе части неравенства.Окончательно получаем (k+1) z ≤ κ z (k) ,∞∞что при |κ| < 1 означает сходимость метода Гаусса-Зейделя.Фактически, в доказательстве Теоремы получена оценкауменьшения чебышёвской нормы погрешности (k+1) z∞≤ κ z (k) ∞ .Коэффициент уменьшения погрешности приближения — это «мерадиагонального преобладания» в матрице СЛАУ.Она измеряется величиной κ, которая определена посредствомXj6=i|aij | ≤ κ |aii |,i = 1, 2, . .

. , n.Итерационный метод Гаусса-ЗейделяТеоремаЕсли в системе линейных алгебраических уравнений Ax = bматрица A является симметричной положительно определённой, тометод Гаусса-Зейделя сходится к решению из любого начальногоприближения.Итерационный метод Гаусса-ЗейделяТеоремаЕсли в системе линейных алгебраических уравнений Ax = bматрица A является симметричной положительно определённой, тометод Гаусса-Зейделя сходится к решению из любого начальногоприближения.Доказательство опускается.Эта теорема является частным случаем теоремыОстровского-Райха, с которой познакомимся далее в курсе.Итерационный метод Гаусса-ЗейделяТеоремаЕсли в системе линейных алгебраических уравнений Ax = bматрица A является симметричной положительно определённой, тометод Гаусса-Зейделя сходится к решению из любого начальногоприближения.Доказательство опускается.Эта теорема является частным случаем теоремыОстровского-Райха, с которой познакомимся далее в курсе.Метод Якоби может расходиться для систем линейных уравненийс симметричными положительно-определёнными матрицами.Итерационный метод Гаусса-ЗейделяМетод Гаусса-Зейделя был сконструирован как модификацияметода Якоби, и, казалось бы, должен работать лучше.Так оно и есть «в среднем», на случайно выбранных системах —метод Гаусса-Зейделя работает несколько быстрее, что можнопоказать математически строго при определённых допущениях насистему.Итерационный метод Гаусса-ЗейделяМетод Гаусса-Зейделя был сконструирован как модификацияметода Якоби, и, казалось бы, должен работать лучше.Так оно и есть «в среднем», на случайно выбранных системах —метод Гаусса-Зейделя работает несколько быстрее, что можнопоказать математически строго при определённых допущениях насистему.Но в целом ситуация не столь однозначна.Для СЛАУ размера 3 × 3 и более существуют примеры, на которыхметод Якоби расходится, но метод Гаусса-Зейделя сходится.Итерационный метод Гаусса-ЗейделяМетод Гаусса-Зейделя был сконструирован как модификацияметода Якоби, и, казалось бы, должен работать лучше.Так оно и есть «в среднем», на случайно выбранных системах —метод Гаусса-Зейделя работает несколько быстрее, что можнопоказать математически строго при определённых допущениях насистему.Но в целом ситуация не столь однозначна.Для СЛАУ размера 3 × 3 и более существуют примеры, на которыхметод Якоби расходится, но метод Гаусса-Зейделя сходится.Но существуют и примеры, когда метод Якоби сходится, а методГаусса-Зейделя расходится.Итерационный метод Гаусса-ЗейделяПо поводу практического применения метода Гаусса-Зейделяможно сказать почти то же самое, что и о методе Якоби.Для решения систем линейных алгебраических уравнений ониспользуется в настоящее время нечасто.Но его идея не утратила своего значения и успешно применяетсяпри построении различных итерационных процессов для решениялинейных и нелинейных систем уравнений.Итерационные методы релаксациидля решения систем линейных уравненийОдним из принципов, который кладётся в основу итерационныхметодов решения систем уравнений, является так называемыйпринцип релаксации (от латинского слова «relaxatio» — уменьшениенапряжения, ослабление).Это специальная организация итераций, при которой на каждомшаге уменьшается какая-либо величина, характеризующаяпогрешность решения.Итерационные методы релаксациидля решения систем линейных уравненийОдним из принципов, который кладётся в основу итерационныхметодов решения систем уравнений, является так называемыйпринцип релаксации (от латинского слова «relaxatio» — уменьшениенапряжения, ослабление).Это специальная организация итераций, при которой на каждомшаге уменьшается какая-либо величина, характеризующаяпогрешность решения.Так как точное решение x⋆ нам неизвестно, то оценить напрямуюпогрешность приближённого решения x̃ не можем.О степени близости x̃ к x⋆ судят на основании косвенныхпризнаков, и важнейшим среди них является невязка решения.ОпределениеДля системы линейных алгебраических уравнений Ax = b неязкаприближённого решения x̃ — это вектор разности левой и правойчастей системы после подстановки в него x̃, т.

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

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