Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 24
Текст из файла (страница 24)
Повторить п. 3 задания для плохо обусловленных матриц (см. подразд. 2.6 лабораторной работы № 1), имеющих порядок от 4 до 40.5. Системы из пп. 2 и 3 необходимо решить двумя методами: методомисключения из лабораторной работы № 1 и методом ортогонального приведения из лабораторной работы № 6. Сравнить точность решения и затратымашинного времени. Результаты представить в виде таблицы и графика.6.
Вычислить матрицу A−1 двумя способами:1) через решение системы AX = I на основе метода исключения Гауссаиз лабораторной работы № 1 (в соответствии со своим вариантом);2) через решение системы AX = I на основе метода ортогонального преобразования (в соответствии со своим вариантом).Сравнить затраты машинного времени и точность обращения способами 1) и 2). Эксперименты провести для матриц порядков от 10 до 100через 10. Для оценки точности в обоих способах воспользоваться формулойиз лабораторной работы (проекта) № 1.1397 Ортогональные преобразования7.16Варианты задания на лабораторный проект № 6По теме «Ортогональные преобразования матриц» студентам предлагается выполнение лабораторной работы — индивидуального проекта № 6.Задание на этот проект содержит 28 вариантов, которые приведены втабл.
7.2 (см. стр. 139). Все варианты различаются по следующим признакам:•четыре варианта заполнения треугольной матрицы R;•три вида ортогональных преобразований:1) отражения Хаусхолдера,2) вращения Гивенса,3) ортогонализация Грама–Шмидта,•две разновидности алгоритма ортогонализации по методу Хаусхолдераи по методу Гивенса:1) столбцово-ориентированный алгоритм,2) строчно-ориентированный алгоритм,•три разновидности ортогонализации по методу Грпма–Шмидта:1) классическая схема,2) модифицированная схема,3) модифицированная схема с выбором ведузего вектора.Если нет других указаний преподавателя, выбирайте ваш вариант втабл.
7.2 (см. стр. 139) по вашему номеру в журнале студенческой группы.1408Итерационные методыПриведен справочный материал, необходимый в подразд. 8.12 для выполнения лабораторного проекта по этой теме (подробнее см. [12]).8.1Итерационные методыЛюбой итерационный метод (ИМ) есть метод последовательных приближений. Он изначально предполагает наличие методической погрешности(ошибки метода) и этим отличается от прямых методов (ПМ), рассмотренных выше, у которых методическая погрешность равна нулю. СходящийсяИМ, — а только такие ИМ и представляют интерес, — обеспечивает стремление этой погрешности к нулю по мере роста числа итераций, n → ∞.ИМ позволяют находить решение с некоторой заранее задаваемой погрешностью и при специальных условиях делают это быстрее, чем ПМ.
Онизапрашивают меньше ресурсов компьютера при решении больших систем.Алгоритмически ИМ более просты, чем ПМ, и в меньшей степени используют структуру матрицы.Главные вопросы для любого ИМ — сходится ли он? какие условия дляэтого нужны? Однако для ИМ важно знать не только теоретический факти условия сходимости. Следующие вопросы — какова скорость сходимости? как можно ее увеличить? Сходимость простых итерационных методовкрайне медленная, особенно, в случае плохо обусловленной матрицы, поэтому эти вопросы крайне важны.Есть два основных «регулятора» скорости ИМ: так называемая лидирующая матрица B и скалярный параметр τ . Если B 6= I, метод называютнеявным ИМ, поскольку решение на новой итерации приходится искать темили иным прямым методом применительно в системе с этой матрицей B, обязанной быть более простой, чем исходная матрица A.
В силу этого неявные8 Итерационные методыметоды алгоритмически более сложны, чем явные ИМ (в которых B = I);однако их преимуществом является существенно более быстрая сходимость.Скалярный параметр τ , как и лидирующую матрицу B, можно выбиратьна каждой итерации, т. е. поставить их в зависимость от текущего номераитерации n. В этом случае стационарный ИМ становится нестационарнымитерационным методом.Кроме методических погрешностей на результат итерационного процесса влияют трансформированные погрешности алгоритма и погрешностиокругления.
Положительным качеством ИМ является то, что при их использовании погрешности округления не накапливаются. Для запуска любогоИМ необходимо задавать начальное приближение к искомому решению.8.2Итерационная формулаИМ могут применяться как для линейных задач, так и для нелинейных.Основой построения любого ИМ является так называемая итерационнаяформула (ИФ), т.
е. формула вида x = ϕ(x). Если она есть, то ИМ записывают в виде xn+1 = ϕ(xn), где n = 0, 1, . . . .Построим ИФ для линейной системыAx = fс обратимой (m × m)-матрицей A = [aij ], i, j = 1, 2, . . . , m, с неизвестным вектором x = (x1, x2, . . . , xm)T и с заданнойправой частью f =T= (f1, f2, .
. . , fm) . Пусть ∀i ∈ {i, j = 1, 2, . . . , m} aii 6= 0.Преобразуем данную систему к видуxi = −i−1Xaijj=2mXfiaijxj −xj + ,aiiaaiij=i+1 iii = 1, 2, . . . , m .(8.1)Условимся считать значение суммы равным нулю, если верхний предел суммирования меньше нижнего. Так, уравнение (8.1) при i = 1 имеет вид:x1 = −mXa1jj=2a11xj +fi.a11В дальнейшем верхний индекс будет указывать номер итерации, например,xn = (xn1 , xn2 , . . . , xnm)T ,1428.3 Метод Якобигде xni — n-я итерация i-й компоненты вектора x. Число итераций ограничивают критерием остановки: либо n < nmax , либо задают малое ε ипроверяют условиеmax | xn+1− xni | < ε .i1≤i≤m8.3Метод ЯкобиВ итерационном методе Якоби исходят из записи системы в виде (8.1),причем итерации определяют формулойxn+1i=−i−1Xaijj=1aiixnjmXaij n fi−xj +,aaiiiij=i+1n = 0, 1, .
. . , nmax,(8.2)i = 1, 2, . . . , m ,где начальные значения x0i , i = 1, 2, . . . , m заданы.8.4Метод ЗейделяИтерационный метод Зейделя определен формулойxn+1i=−i−1Xaijj=1aiixn+1jn = 0, 1, . . . , nmax,mXaij n fi−xj +,aaiiiij=i+1(8.3)i = 1, 2, . . . , m ,где начальные значения x0i , i = 1, 2, . . . , m заданы.Для наглядности запишем первые два уравнения системы (8.3):xn+11=−mXa1jj=2a11xnj +f1,a11(8.4)mxn+12X a2jf2a21−xnj +.= − xn+11a22aa2222j=2(8.5)Первую компоненту xn+1вектора xn+1 находят из (8.4).
Для этого ис1пользуют вектор xn и значение f1. Для вычисления xn+1по выражению2n+1(8.5) используют только что найденное значение x1 и известные значенияxnj , j = 3, . . . , m от предыдущей итерации. Таким образом, компоненты xn+1in+1вектора xнаходят из уравнения (8.3) последовательно, начиная с i = 1.1438 Итерационные методы8.5Матричная запись методов Якоби и ЗейделяСопоставительный анализ итерационных методов упрощается, если записать их не в координатной, а в матричной форме. Представим матрицу A ввиде суммы трех матрицA = A1 + D + A2 ,(8.6)где D = diag [a11, a22, .
. . , amm]; — диагональная матрица с той же главнойдиагональю, что и матрица A, матрица A1 — нижняя треугольная и матрица A2 — верхняя треугольная, обе с нулевыми главными диагоналями.Используя «расщепление» (8.6), перепишем систему Ax = f в видеx = −D−1 A1x − D−1 A2x + D−1f .Отсюда видно, что метод Якоби (8.2) представлен формулойxn+1 = −D−1 A1xn − D−1 A2xn + D−1 f ,или, что то же самое, формулойDxn+1 + (A1 + A2)xn = f ,(8.7)а метод Зейделя (8.3) — формулойxn+1 = −D−1 A1xn+1 − D−1 A2xn + D−1 f ,или, что то же самое, формулой(D + A1 )xn+1 + A2 xn = f .(8.8)Учитывая (8.6), методы (8.7) и (8.8) запишем, соответственно, в видеD(xn+1 − xn ) + Axn = f ,(8.9)(D + A1 )(xn+1 − xn) + Axn = f .(8.10)Эта запись показывает, что если итерационный метод сходится, то он сходится к решению исходной системы уравнений.В методы (8.9) и (8.10) можно ввести итерационный параметр τn+1 следующим образом:xn+1 − xn+ Axn = f ,Dτn+11448.6 Каноническая форма одношаговых ИМxn+1 − xn+ Axn = f .(D + A1)τn+1Приведенные выше методы Якоби и Зейделя относятся к одношаговымитерационным методам.
В таких методах для нахождения xn+1 используют одну предыдущую итерацию xn. Многошаговые итерационные методыопределяют xn+1 через значения xk на двух и более предыдущих итерациях, так что l-шаговый ИМ выглядит как некоторая зависимость xn+1 == ϕ(xn, . . . , xn−l+1) .8.6Каноническая форма одношаговых ИМКанонической формой одношагового итерационного метода для решениясистемы Ax = f называют его представление в видеBn+1xn+1 − xn+ Axn = f ,τn+1n = 0, 1, . . . , nmax .(8.11)Здесь Bn+1 — лидирующая матрица, задающая тот или иной итерационный метод, τn+1 — итерационный параметр.
Предполагается, чтодано начальное приближение x0 и что существуют Bn+1 и τn+1, n == 0, 1, . . . , nmax. Тогда из уравнения (8.11) можно последовательно определить все xn+1, n = 0, 1, . . . , nmax.Для нахождения xn+1 по известным f и xn достаточно решить системуBn+1xn+1 = Fnс правой частью Fn = (Bn+1 − τn+1A)xn + τn+1f .Стационарный ИМ определяется выполнением двух условий: Bn+1 == B = const и τn+1 = τ = const; иначе имеем нестационарный ИМ.8.7Методы простой итерации, Ричардсона и ЮнгаМетодом простой итерации называют явный методxn+1 − xn+ Axn = fτс постоянным параметром τ .
Явный методxn+1 − xn+ Axn = fτn+1(8.12)(8.13)1458 Итерационные методыс переменным τn+1 есть итерационный метод Ричардсона. Юнг усовершенствовал метод Зейделя, введя в него параметр ω > 0. Этот метод получилназвание метод верхней релаксации:xn+1 − xn+ Axn = f .(D + ωA1 )ω(8.14)Расчетная схема для (8.14) с учетом (8.6) получается в виде(I + ωD−1 A1 )xn+1 = ((1 − ω)I − ωD−1 A2)xn + ωD−1 f .В покомпонентной записи имеемxn+1i+ωi−1Xaijj=1aiixn+1j= (1 −ω)xnimXfiaij n−ωxj + ω ,aaiij=i+1 iii = 1, 2, . . .
, m., например, первые два:Последовательно, начиная с i = 1, находим все xn+1ixn+11= (1 −ω)xn1−ωmXa1jj=2a11xnj + ωf1,a11mxn+128.8X a2ja21f2n= −ω xn+1+(1−ω)x−ωxnj + ω.21a11aa2222j=3Сходимость итерационных методовЗапишем стационарный одношаговый итерационный метод (8.11) в терминах погрешности z n = xn − x:z n+1 − z n+ Az n = 0 ,BτТеорема 8.1 ( [12]).ствоn = 0, 1, . . . ,z 0 = x0 − x .(8.15)Пусть A = AT > 0, τ > 0 и выполнено неравенB − 0.5τ A > 0 .(8.16)Тогда итерационный метод (8.11) сходится.Следствие 8.1. Пусть A = AT > 0. Тогда метод Якоби сходится [12],если A — матрица с диагональным преобладанием, т. е. при условииX| aij | ,i = 1, 2, . . .
, m .(8.17)aii >j6=i1468.9 Скорость сходимости итерационных методовСледствие 8.2.Пусть A = AT > 0. Тогда метод верхней релаксацииxn+1 − xn+ Axn = f(D + ωA1 )ωсходится при условии 0 < ω < 2. В частности, метод Зейделя сходится [12].Пусть A = AT > 0. Тогда для метода простойСледствие 8.3.итерацииxn+1 − xn+ Axn = fτнеобходимым и достаточным условием сходимости является неравенство0 < τ < 2/λmax ,где λmax — наибольшее по абсолютному значению собственное число матрицы A, называемое также спектральным радиусом ρ(A) матрицы A [12].Сходимость итерационного метода (8.11) означает, что z n → 0 в некоторой норме при n → ∞. Переписав уравнение (8.15), получим:z n+1 = Sz n ,n = 0, 1, . .
. ,(8.18)гдеS = I − τ B −1A(8.19)называют переходной матрицей погрешности от n-й итерации к (n + 1)-й.Теорема 8.2 ( [12]).Итерационный методxn+1 − xn+ Axn = f ,Bτn = 0, 1, . . . ,(8.20)сходится при любом начальном приближении тогда и только тогда, когдавсе собственные значения матрицы (8.19) по модулю меньше единицы.8.9Скорость сходимости итерационных методовТеорема 8.2 о сходимости имеет принципиальное значение и накладываетминимальные ограничения на матрицы A и B. Однако ее непосредственноеприменение к конкретным итерационным методам не всегда возможно, таккак исследование спектра матрицы (8.19) является более трудоемкой задачей, чем решение исходной системы Ax = f .1478 Итерационные методыБудем рассматривать решение x системы и последовательные приближения xn как элементы евклидова пространства, а матрицы A, B и другие —как операторы, действующие в нем.Замечание 8.1.Для двух симметрических матриц A и B неравенство A ≥ B означает, что (Ax, x) ≥ (Bx, x) для всех x ∈ E.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
