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

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

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

Если C — неособенная n × n-матрица иCv = λv,тоv = λC −1 v.Далее, так как λ 6= 0 в силу неособенности C, получаем отсюдаC −1 v = λ−1 v.Если A — симметричная положительно определённая матрицаи известна нижняя граница её спектра µ > 0, то из доказанногоПредложения следует, что −1 A = λmax (A−1 ) =2−1≤ µ−1 .λmin (A)Такова ситуация с численным решением некоторых популярныхуравнений математической физики (уравнением Лапласа и егообобщениями, к примеру).Для них дискретные аналоги соответствующих дифференциальныхоператоров хорошо изучены и известны оценки их собственныхзначений.Если матрица системы имеет диагональное преобладание,то для оценивания kA−1 k можно воспользоваться теоремойАлберга-Нильсона.Теорема Алберга-НильсонаПусть A = (aij ) — n × n-матрица с диагональным преобладанием и()Xα := min |aii | −|aij | .1≤i≤nТогда kA−1 k∞ ≤ α−1 .j6=iВ общем случае нахождение kA−1 k или хотя бы разумной оценкидля kA−1 k в какой-то норме, которое было бы менее трудоёмким,чем решение исходной системы уравнений, являетсянетривиальным делом.В общем случае нахождение kA−1 k или хотя бы разумной оценкидля kA−1 k в какой-то норме, которое было бы менее трудоёмким,чем решение исходной системы уравнений, являетсянетривиальным делом.Краткий обзор существующих численных процедур для этой цели,которые называются «оценщиками обусловленности», а такжедальнейшие ссылки на литературу можно найти, например, в книгеJ.W.

DemmelApplied numerical linear algebra.– Philadelphia: SIAM, 1997.Деммель Дж.Вычислительная линейная алгебра.– Москва: Мир, 2001,более точно, в §2.4.3.Оценка погрешности приближённого решенияДля конкретных численных методов оценка погрешностиприближённого решения иногда может быть выведенаиз свойств этих методов.Например, в стационарных одношаговых итерационных методахпоследовательность погрешностей приближений своими свойствамиочень близка к геометрической прогрессии.Этим обстоятельством можно воспользоватьсядля получения желаемых оценок.Пусть задан сходящийся стационарный одношаговый итерационныйметодx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . ,в котором kCk < 1 для некоторой матричной нормы.Пусть задан сходящийся стационарный одношаговый итерационныйметодx(k+1) ← Cx(k) + d,k = 0, 1, 2, .

. . ,в котором kCk < 1 для некоторой матричной нормы.НапомнимПредложениеДля любой квадратной матрицы A и любого ǫ > 0 существуеттакая подчинённая матричная норма k · kǫ , чтоρ(A) ≤ kAkǫ ≤ ρ(A) + ǫ.Как следствие, допущение kCk < 1 не ограничивает общностинашего рассмотрения.Как оценить отклонение по норме очередного приближения x(k) отпредела x⋆ := limk→∞ x(k) , не зная самого этого предела и наблюдаялишь за итерационной последовательностью x(0) , x(1) , . .

. , x(k) , . . . ,порождённой процессомx(k+1) ← Cx(k) + d,k = 0, 1, 2, . . . ?Как оценить отклонение по норме очередного приближения x(k) отпредела x⋆ := limk→∞ x(k) , не зная самого этого предела и наблюдаялишь за итерационной последовательностью x(0) , x(1) , . . . , x(k) , . . . ,порождённой процессомx(k+1) ← Cx(k) + d,k = 0, 1, 2, .

. . ?Как и прежде, имеемx(k) = Cx(k−1) + d,x⋆ = Cx⋆ + d.Вычитание второго равенства из первого даётx(k) − x⋆ = C x(k−1) − x⋆ .(6)Перенесём x(k) в правую часть полученного соотношения, а затемдобавим к обеим частям по x(k−1) :x(k−1) − x⋆ = x(k−1) − x(k) + C x(k−1) − x⋆ .Перенесём x(k) в правую часть полученного соотношения, а затемдобавим к обеим частям по x(k−1) :x(k−1) − x⋆ = x(k−1) − x(k) + C x(k−1) − x⋆ .Возьмём от обеих частей этого равенства векторную норму, котораясогласована с используемой матричной нормой для C.Применяя затем неравенство треугольника, приходим к оценке (k−1)x− x⋆ ≤ x(k) − x(k−1) + kCk · x(k−1) − x⋆ .Перенесение в левую часть второго слагаемого из правой части ипоследующее деление обеих частей неравенства на положительнуювеличину (1 − kCk) даёт (k−1)x− x⋆ ≤ (k)1x − x(k−1) .1 − kCk(7)Перенесение в левую часть второго слагаемого из правой части ипоследующее деление обеих частей неравенства на положительнуювеличину (1 − kCk) даёт (k−1)x− x⋆ ≤ (k)1x − x(k−1) .1 − kCkС другой стороны, вспомним, что из (6) следует (k)x − x⋆ ≤ kCk · x(k−1) − x⋆ .(7)Перенесение в левую часть второго слагаемого из правой части ипоследующее деление обеих частей неравенства на положительнуювеличину (1 − kCk) даёт (k−1)x− x⋆ ≤ (k)1x − x(k−1) .1 − kCkС другой стороны, вспомним, что из (6) следует (k)x − x⋆ ≤ kCk · x(k−1) − x⋆ .(7)Подставляя сюда вместо kx(k−1) − x⋆ k оценку сверху (7), получаемокончательно (k) x − x⋆ ≤kCk x(k) − x(k−1) .1 − kCkВыведенная оценка может быть использована на практикедля оценки погрешности какого-то приближения изитерационной последовательности,для определения момента окончания итераций, т.

е. того,достигнута ли желаемая точность приближения к решению.Пример.Рассмотрим систему линейных алгебраических уравнений!!2 10x=,3 45точное решение которой равно (−1, 2)⊤ .Для её решения организован итерационный метод Гаусса-Зейделя.Начальным приближением взято x(0) = (0, 0)⊤ .Через сколько итераций компоненты очередного приближенияк решению станут отличаться от точного решения не более,чем на 10−3 ?Исследуемый вопрос требует чебышёвской нормы k · k∞для измерения отклонения векторов друг от друга.Исследуемый вопрос требует чебышёвской нормы k · k∞для измерения отклонения векторов друг от друга.Вспомним матричное представлениеитерационного метода Гаусса-Зейделя:x(k+1) = −(D + L̃)−1 Ũ x(k) + (D + L̃)−1 b,k = 0, 1, 2, .

. . .Поэтому матрица оператора перехода нашего итерационногопроцесса есть−2 03 4!−10 10 0!=0 −0.50 0.375!,и её ∞-норма равна 0.5.Следовательно, в оценкеимеем (k) x − x⋆ ≤kCk x(k) − x(k−1) .1 − kCk0.5kCk== 1,1 − kCk1 − 0.5и потому должно быть справедливым неравенство (k)x − x⋆ ≤ x(k) − x(k−1) .∞∞Оно показывает, что в наших итерациях компоненты очередногоприближения отличаются от компонент точного решения не более,чем компоненты приближений друг от друга.Запустив итерации Гаусса-Зейделя, мы можем видеть, чтоx(0)=(0, 0)⊤ ,x(1)=(0, 1.25)⊤ ,x(2)=(−0.625, 1.71875)⊤ ,······x(8)=(−0.998957, 1.999218)⊤ ,x(9)=(−0.999609, 1.999707)⊤ ,т.

е. 9-я итерация отличается от предыдущей 8-й меньше чем на10−3 , и потому согласно нашей оценке на этой итерации получаемтребуемую погрешность.Проконтролировать ответ можно сравнением x(9) с известным намточным решением (−1, 2)⊤ .Как хорошо видно из примера, практическая реализацияпредложенной методики оценки погрешности итерационногорешения может столкнуться с двумя трудностями:Во-первых, непростым является определение матрицы C(которая может и не задаваться в явном виде).Во-вторых, выбор нормы k · k, в которой kCk < 1,также может быть неочевидным.Теоретически такая норма должна существовать, еслиитерационный процесс сходится из любого начальногоприближения, но её конкретный выбор в общем случаенепрост.Конец лекций нашего курса.

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

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