Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 8

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

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

е.1/2 2 −231/2 2 −23 −1/41/2 1/2 2 −1 2 −1  =⇒  −1/4, −1−11/3 −2  ❸  −1/3 −1/31/3 −2 −3/4 −1/2 −2/3 1/4 −1/121/6 −2/3 1/4 и на этапе ❹ пересчитываются только элементы a41 , a42 и a43, т. е.1/2 2 −231/2 2 −23 −1/41/2 1/2 2 −1 2 −1  =⇒  −1/4. −1/3 −1/31/3 −2  ❹  −1/3 −1/31/3 −2 −1/121/6 −2/3 1/4 −1/481/24 −1/6 1/4 Построение алгоритма вычисления матрицы Ū −1 проводится аналогично.Для Ū свойство суперпозиции означает, что произведение Ū = Ū4Ū3Ū2Ū1может быть получено не перемножением элементарных матриц Ū4, Ū3, Ū2, Ū1,442.5 Вычисление обратной матрицыа суперпозицией (постановкой на свои позиции) нетривиальных столбцовэлементарных матриц-сомножителей, т. е.ŪŪ4Ū3 1 2 −2 3131−21 2 −1 1−1 1 2=1 −2  1 −2 1111Ū21 2111,где учтено, что крайний справа сомножитель Ū1 равен единичной матрице,так как по построению Ū — верхнетреугольная матрица с единичной диагональю.Руководствуясь правилом обращения произведения матриц, Ū −1 найдемкак результат перемножения следующих обратных матриц:Ū2−11 −211Ū3−112 1 −2× 1 1 1 × Ū4−11−311.1 21(2.16)Здесь уже отражен тот факт, что обращение элементарных матрицŪ4, Ū3, Ū2 сводится в простой замене знака на противоположный у каждогонетривиального (внедиагонального) элемента.В действительности же это означает, что сначала — на этапе ① для верхнетреугольной части и на уже расмотренном этапе ❶ для нижнетреугольнойчасти (2.15) — результирующий массив из (2.14) пересчитывают по указанным правилам для вычисления L̄−1 и Ū −1 , приводя его к следующему стартовому виду: 1/2 −2 2 −32 2 −23 1 2 2 −1  ①  −1/21/2 −2 1  =⇒ .(2.17)3 23 −2  ❶  −3/2 −2/21/3 2 2 124−2/2 −1/2 −2/3 1/4 Одинаковые номера этапов ① и ❶ здесь подсказывают, что эти подготовительные действия над верхней и нижней частями массива могут бытьсовмещены по времени в одном цикле.Процесс поэтапного перемножения в выражении (2.16) отразим втабл.

2.3.452 Стандартные алгоритмы LU-разложенияТаблица 2.3. Поэтапное перемножение Ū2−1 (Ū3−1 Ū4−1 )Ū2−11 −211Ū2−11 −211Ū3−112 1 −2× 1 1 1 × (Ū3−1Ū4−1 ) 12 1 1 −2 −3× 1 211Ū2−1(Ū3−1Ū4−1)1 −2 6 71 −2 −31 21Ū4−11−3111 21⇐= ②⇐= ③Из табл. 2.3 видно, что после получения верхней треугольной части в(2.17) пересчитывают только следующие элементы: на этапе ② — a14 , a24 ина этапе ③ — a13 , a14 .

Совмещая операции ② и ❷ после (2.17), получаем1/2 −2 211/2 −2 2 −3 −1/2② 1/2 −2 1/2 −2 −3 1  =⇒. −1/4 −3/2 −2/21/3 −11/3 2  ❷  −12 −2/2 −1/2 −2/3 1/4 −3/4 −1/2 −2/3 1/4 Совмещение операций ③ и ❸1/2 −2 211/2 −2 67 −1/4③ 1/2 −2 −3 1/2 −2 −3 =⇒ −1/4 −1−11/3 1/3 2  ❸  −1/3 −1/32−3/4 −1/2 −2/3 1/4 −1/121/6 −2/3 1/4завершает операции над верхней треугольной частью, а для нижней треугольной части завершение ❹ показано отдельно на стр.

44.462.6 Плохо обусловленные матрицы2.6Плохо обусловленные матрицыСледующие матрицы [11] часто используют для испытания разработанных программ решения систем и обращения матриц в особо сложных условиях, т. е. в таких случаях, когда матрица системы близка к вырожденнойматрице.Обозначения: aij — элемент матрицы A, n — ее порядок.1. Матрица Гильберта.aij = 1/(i + j − 1).2.

Матрица A с элементами:aii = 1 для i = 1, 2, . . . , 20;aii+1 = 1 для i = 1, 2, . . . , 19;aij = 0 для остальных значений i и j.5 4 7 5 6 7 5 4 12 8 7 8 8 6  7 8 10 9 8 7 7 3. A =  5 7 9 11 9 7 5 . 6 8 8 9 10 8 9  7 8 7 7 8 10 10 5 6 7 5 9 10 104. Матрица A с элементами:aii = 0.01/(n − i + 1)/(i + 1);aij = 0 для i < j;aij = i(n − j) для i > j.5.

Матрица из пункта 4, ноaij = j(n − i) для i < j.RS6. A = TTSRSTTSRSTT ,S RR=ctg θcosec θ,− cosec θ ctg θ472 Стандартные алгоритмы LU-разложенияS=1 − ctg θ cosec θ,− cosec θ 1 + ctg θT =1 1.1 1Вычисления проводить при θ близком к нулю или π.7. Матрица с параметром α:aii = α|n−2i|/2;a1j = aj1 = a11 /αj ;anj = ajn = ann /αj ;aij = 0 для остальных значений i и j.8. aij = ei·j·h .Вычисления проводить при h близких к нулю или 1000.9. aij = c + log2 (i · j).Вычисления проводить при больших c.0.9143 · 10−4000−40.87620.7156 · 100010. A = 0.79430.81430.9504 · 10−400.80170.61230.71650.7123 · 10−42.7.Задание на лабораторный проект № 1Написать и отладить программу, реализующую ваш вариант методаисключения с выбором главного элемента, для численного решения системлинейных алгебраических уравнений Ax = f , вычисления det A и A−1.Предусмотреть сообщения, предупреждающие о невозможности решенияуказанных задач с заданной матрицей A.Отделить следующие основные части программы:а) подпрограмму факторизации матрицы A, отвечающую вашему варианту метода исключения;б) подпрограмму решения систем линейных алгебраических уравнений;в) подпрограмму вычисления определителя матриц;г) две подпрограммы обращения матриц;д) сервисные подпрограммы.482.7 Задание на лабораторный проект № 1Уделить особое внимание эффективности программы (в смысле экономии оперативной памяти).

Предусмотреть пошаговое выполнение алгоритмаисключения с выводом результата на экран.Выполнить следующие пункты задания.1. Провести подсчет фактического числа выполняемых операций умножения и деления при решении системы линейных алгебраических уравнений,сравнить его с оценочным числом (n3/3).2. Определить скорость решения задач (решение систем линейных алгебраических уравнений, обращение матриц) с учетом времени, затрачиваемогона разложение матрицы.

Для этого спроектировать и провести эксперимент,который охватывает матрицы порядка от 5 до 100 (через 5 порядков). Представить результаты в виде таблицы и графика зависимости времени выполнения (в минутах и секундах) от порядка матриц. Таблицу и график вывестина экран.3. Оценить точность решения систем линейных алгебраических уравнений, имеющих тот же самый порядок, что и задачи из п.

2. Для этого сгенерировать случайные матрицы A, задать точное решение x∗ и образоватьправые части f = Ax∗. Провести анализ точности вычисленного решения xот порядка матрицы. Результаты представить в виде таблицы и графика.Для заполнения матрицы A использовать случайные числа из диапазонаот −100 до 100. В качестве точного решения взять вектор x∗ = (1, 2, . . . , n)T ,где n — порядок матрицы. Для оценки точности использовать норму вектораkxk∞ = max(|xi|).i(2.18)4. Повторить пункт 3 задания для плохо обусловленных матриц (см. подразд.

2.6), имеющих порядок от 4 до 40 с шагом 4.5. Вычислить матрицу A−1 следующими двумя способами.Способ 1 — через решение системы AX = I, где I — единичная матрица.Способ 2 — через разложение матрицы A в произведение элементарныхматриц, обращение которых осуществляется отдельными процедурами, а ихпроизведение дает матрицу A−1.Сравнить затраты машинного времени (по числу операций) и точностьобращения матриц при использовании указанных способов 1 и 2.

Эксперименты провести для случайных матриц порядков от 5 до 100 через 5. Дляоценки точности в обоих способах использовать оценочную формулу−1−1−1kA−1т − Aпр k ≤ kI − AAпр k · kAk .(2.19)492 Стандартные алгоритмы LU-разложенияИспользовать норму матрицы типа «бесконечность», т. е. вычислять еепо следующему выражению:!nXkAk∞ = max|aij | ,(2.20)ij=1−1где A−1т — точное значение обратной матрицы, а Aпр — приближенное значение, полученное в результате обращения каждым из способов 1 и 2.6. Провести подсчет фактического числа выполняемых операций умножения и деления при обращении матриц первым и вторым способами, сравнитьего с оценочным числом (n3).Замечание 2.8. По ходу проведения численных экспериментов наэкран дисплея должны выводиться следующие таблицы.Решение систем линейных алгебраических уравнений:ПорядокВремяТочностьТеоретическоеРеальноечисло операций число операцийАналогичная таблица должна быть построена для плохо обусловленныхматриц.Обращение матриц:ПорядокВремяТочностьЧисло операцийспос.

1 спос. 2 спос. 1 спос. 2 спос. 1 спос. 2 теорет.Замечание 2.9. Результаты экспериментов необходимо вывести наэкран в форме следующих графиков. Для случая обращения матриц припостроении графиков использовать данные из второй таблицы.Графики решения систем линейных алгебраических уравнений:•••50зависимость реального и оценочного числа операций от порядка матрицы (для разных графиков использовать разные цвета);зависимость времени решения от порядка матриц;зависимость точности решения от порядка матриц. При построении графиков использовать данные из первой таблицы.

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

Список файлов книги