Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 26
Текст из файла (страница 26)
. . , Aj−1x .В настоящее время алгоритмы Крылова с предобусловливанием применяются в большинстве итерационных методов решения больших разреженныхлинейных систем [126]. Успешной альтернативой методам Крылова являются многосеточные методы, по которым за последние 30–40 лет появилосьогромное число публикаций [102, 118, 126, 144].Вместе с этими мощными ветвями роста, в практике решения линейных систем итерационными методами встречаются решения, которые могутбыть классифицированы как Inventive Math. Это решения, по которым покане найдено строгих доказательств, но которые подтверждают свою работоспособность методом широкого вычислительного эксперимента.
Примером такого подхода является метод делинеаризации для линейных систем[140, 141, 142].8.12Задание на лабораторный проект № 7Написать и отладить программу, реализующую ваш вариант задания в соответствии с табл. 8.1 (см. ниже стр. 159), включающий два итерационныхметода для численного решения систем линейных алгебраических уравнений Ax = f с квадратной матрицей A и отыскания обратной матрицы A−1.Предусмотреть сообщение о невозможности решения указанных задач из-запревышения допустимого числа итераций.
Отделить основные части программы:а) подпрограмму решения систем линейных алгебраических уравнений;б) подпрограмму обращения матриц;1568.12 Задание на лабораторный проект № 7в) сервисные подпрограммы.Уделить особое внимание эффективности программы (в смысле экономииоперативной памяти и скорости решения указанных выше задач). Предусмотреть пошаговое выполнение алгоритма с выводом xk на каждой итерации (для тестовой задачи небольшой размерности, см.
ниже п. 4).В качестве ε (см. критерий остановки в подразд. 8.2) для обоих итерационных методов использовать погрешность решения данной системы линейных алгебраических уравнений (СЛАУ) методом исключения переменныхиз лабораторной работы № 1.Выполнить следующие пункты задания:1. Провести подсчет фактического количества операций умножения иделения, выполняемых при решении системы линейных алгебраическихуравнений c выводом результата на экран. Сравнить с методом исключения переменных из лабораторной работы № 1. Вывести таблицу и график.2.
Оценить скорость решения задач, т. е. определить время, затраченное на решение СЛАУ, и время, затраченное на обращение матриц. Дляэтого спроектировать и провести эксперимент, который охватывает матрицыпорядка от 10 до 200 (через 10 порядков).
Представить результаты в видетаблицы и графика зависимости времени выполнения от порядка матриц длятрех алгоритмов (двух итерационных методов, соответствующих варианту,и методу исключения переменных из лабораторной работы № 1). Таблицу играфики вывести на экран.3. Оценить точность решения систем линейных алгебраических уравнений, указанных в п. 2. Для этого сгенерировать случайные матрицы A,задать точное решение x∗ и образовать правые части f = Ax∗. Провестианализ точности вычисленного решения x от порядка матрицы для трехалгоритмов (аналогично п. 2). В качестве точного решения взять векторx∗ = (1, 2, . . . , m)T , где m — порядок матрицы. Для оценки точности решения использовать норму вектораkxk = max | xi | .iРезультаты по п.
3 представить в виде таблицы и графиков.Замечание 8.2. Для проведения вычислительного эксперимента попп. 2 и 3 применять симметрические положительно определенные матрицы Aс диагональным преобладанием. Для заполнения матрицы A использоватьслучайные числа из диапазона от −100 до 100. Сначала заполнить нижнюю треугольную часть матрицы A, т. е. элементы aij , где i > j. Верхнюю1578 Итерационные методытрегольную часть, где i < j, заполнить симметрично нижней части. Затемзаполнить диагональ.
В качестве диагонального элемента aii , i = 1, 2, . . . , m,выбрать случайное число из интервалаXX|aij | + 101 ,|aij | + 1,j6=ij6=iчтобы обеспечить выполнение условияX|aij | + 1,aii ≥j6=iгарантирующего положительную определенность матрицы A.4. До проведения вычислительного эксперимента по пп. 2 и 3 выполнитьотладку программы.
Для отладки программы, а также для сравнительноготестирования двух заданных итерационных методов использовать следующую тестовую задачу [99]:40A=110401104011,0412f = 3 ,4−41/209 = −0.196172 53/209 = 0.253589 x∗ = 167/209 = 0.799043 .206/209 = 0.9856465. Для тех вариантов задания, в которых присутствует метод Юнга (верхней релаксации), провести специальный вычислительный эксперимент решения тестовой задачи по п. 4. Цель этого эксперимента — исследование скорости сходимости метода в зависимости от коэффициента релаксации ω вформуле (8.14).Изменение параметра ω организовать с шагом ∆ω = 0.05 равномернов интервале теоретической сходимости метода: 0 < ω < 2, т.
е. по алгоритму:ω0 := ωstartДля i = 0, 1, . . . , 20 выполнятьωi+1 := ωi + ∆ωСтартовое значение задавать с клавиатуры, например, ωstart = 0.50.6. Повторить п. 3 задания для плохо обусловленных матриц (см. подразд. 2.6 лабораторной работы № 1), имеющих порядок от 4 до 40.1588.13 Варианты задания на лабораторный проект № 7Таблица 8.1.
Варианты задания на лабораторный проект № 7Вариантыитерационныхметодовabcdefga-13141234b--155678c---9101112a——c—d—e—f—g—bметодметодметодметодметодметодметодЯкоби;Зейделя;Юнга;минимальных невязок;минимальных поправок;скорейшего спуска;сопряженных градиентов.7. Вычислить матрицу A−1 двумя способами:1) через решение системы AX = I на основе метода исключения Гауссаиз лабораторной работы № 1 (в соответствии со своим вариантом);2) через решение системы AX = I на основе любого из двух заданныхитерационных методов.Сравнить затраты машинного времени и точность обращения способами1) и 2).
Эксперименты провести для матриц порядков от 10 до 100 через10, сгенерированных согласно замечанию 8.2. Для оценки точности в обоихспособах воспользоваться формулой из лабораторной работы (проекта) № 1.8.13Варианты задания на лабораторный проект № 7По теме «Итерационные методы» студентам предлагается 15 вариантовлабораторной работы № 7, сведенных в табл.
8.1.Если нет других указаний преподавателя, выбирайте ваш вариант изтабл. 8.1 по вашему номеру в журнале студенческой группы.1599Фонд задачЦелью настоящего раздела является формирование и проверка у студентов, изучающих курс «Численные методы», базовых навыков в областирешения задач вычислительной линейной алгебры. Предлагаемые в этомразделе задачи охватывают широкий спектр методов: гауссово исключениепеременных, итерационные методы решения систем линейных алгебраических уравнений, включая методы вариационного типа, факторизацию положительно определенных матриц и ортогональные преобразования.
Приводимые ниже задачи могут быть использованы как для практических занятий и контрольных работ в аудитории, так и для самостоятельной работыстудента, а также для проверки практических навыков студентов во времяэкзамена. Данный материал позволяет не только проверить знание базовыхалгоритмов в области вычислительной линейной алгебры, но и определитьуровень владения вычислительной техникой для решения тех или иных прикладных задач. Большое разнообразие и количество задач создает возможность формирования индивидуального задания для каждого студента.9.1Типовые задачиНачнем прежде всего, с разбора типовых задач. В соответствии с вышесказанным настоящее учебное пособие содержит задачи по следующимпяти темам: метод исключения Гаусса, итерационные методы, итерационные методы вариационного типа, разложение Холесского для симметричныхположительно определенных матриц и методы ортогонального приведения.Задача 1 (см.
ниже) является типичным представителем задач на методГаусса исключения переменных. Целью задачи является проверка знаниябазовых алгоритмов для разложения невырожденной матрицы в произведение нижней и верхней треугольных матриц, а также для решения системы9.1 Типовые задачилинейных уравнений с разложенной матрицей коэффициентов и обращения матрицы. Разнообразие задач достигается за счет вовлечения различных вариантов разложения (см. лабораторную работу № 1, подразд. 2.8) ииспользования разных исходных матриц.Задача 1Для матрицывыполнить следующее:2 1 1A= 6 2 1−2 −2 −1а. Построить L̄U -разложение матрицы A (L̄ с единицами на главной диагонали).б. С помощью L̄U -разложения матрицы A решить систему линейныхуравненийAx = b,где вектор b = (0, 3, 1)T .в.
С помощью L̄U -разложения найти матрицу A−1 и вычислить числоMA обусловленности матрицы A в норме k·k∞ = max {|xi|}, x ∈ R3 .i=1,2,3Задача 2 является типичным представителем задач на итерационные методы решения систем линейных алгебраических уравнений. Целью задачиявляется проверка знания базовых итерационных алгоритмов, а также необходимых и достаточных условий их сходимости и критериев для оценкиточности решения. Разнообразие задач достигается за счет вовлечения различных итерационных методов, изучаемых в курсе «Численные методы», ииспользования разных исходных матриц.Задача 2Для системы линейных алгебраических уравнений видаAx = b,где матрица5 −1A = −1 40 1012и вектор b = (4, 2, −1)T , выполнить следующее:1619 Фонд задача.
Сформулировать метод Зейделя в координатном и каноническом виде.б. Определить является ли он сходящимся с нулевым начальным приближением, т. е. x0 = (0, 0, 0)T ? Ответ обосновать.в. Вычислить две итерации по методу Зейделя и найти апостериорнуюоценку ошибки на каждой из них в норме k·k∞ = max {|xi|}, x ∈ R3 .i=1,2,3Следующая задача посвящена итерационным методам вариационноготипа. Ее целью является проверка знания алгоритмов построения итерационных методов вариационного типа, формул для вычисления оптимального итерационного параметра и критериев для оценки точности решения.Разнообразие задач достигается за счет вовлечения различных способов построения итерационных методов вариационного типа, изучаемых в курсе«Численные методы», и использования разных исходных матриц.Задача 3Для системы линейных алгебраических уравнений видаAx = b,где матрица5 −1A = −1 40 1012и вектор b = (4, 2, −1)T , выполнить следующее:а.
На основе метода Зейделя сформулировать неявный метод скорейшегоспуска в каноническом виде.б. Определить оптимальный параметр τ1 для нулевого начального приближения, т. е. x0 = (0, 0, 0)T ?в. Вычислить одну итерацию и найти апостериорную оценку ошибки внорме k · k∞ = max {|xi |}, x ∈ R3 .i=1,2,3Задача 4 является типичным представителем задач на разложение Холесского для симметричных положительно определенных матриц. Целью1629.1 Типовые задачизадачи является проверка знания базовых алгоритмов Холесского для разложения симметричной положительно определенной матрицы, а также способов решения системы линейных уравнений с разложенной матрицей коэффициентов и обращения матрицы.
Разнообразие задач достигается за счетвовлечения различных вариантов разложения Холесского (см. лабораторную работу № 5, подразд. 6.8) и использования разных исходных матриц.Задача 4Для матрицывыполнить следующее:18 −10 3 10 −10 105 −8 25 P =3 −8 1 0 10 25 0 25а. Построить U DU T -разложение матрицы P (U — верхняя треугольнаяматрица с единицами на главной диагонали, D — диагональная матрица с положительными элементами на диагонали).б.
С помощью U DU T -разложения матрицы P решить системуP x = b,c вектором b = (21, 112, −4, 60)T .в. С помощью разложения и решения системы найти величину квадратичной формы J(x) = xT P x, где x — решение из п.б.Последняя задача этого раздела посвящена соответственно последнейтеме, а именно, — методам ортогонального разложения матриц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
