метода Волощенко (551678), страница 9
Текст из файла (страница 9)
5.1. Существенным недостатком этого алгоритма является отсутствие контроля диагональных коэффициентов ааа . Равенство нулю хотя бы одного такого коэффициента приводит к аварийному останову программы. Поэтому на практике используют модифицированные алгоритмы метода Гаусса. Для исключения аварийного останова программы в алгоритме предусматривают перестановку уравнений в цикле прямого хода таким образом, чтобы коэффициенты а„„были отличны от нуля.
Отсутствие нулевых диагональньгх элементов в матрице А еще не гарантирует получение требуемого решения, так как погрешность результата, как показывает опыт„существенно зависит от абсолютных значений диагональных элементов. Поэтому обычно на алгоритм накладывают более жесткое требование — из всех оставшихся в з-ом столбце коэффициентов выбрать наибольший по модулю и переставить уравнения так, чтобы этот коэффициент оказался на месте элемента а„„(такой метод принято называть методом с выбором главного элемента).
Пусть имеем систему уравнений в матричной форме (5.1). Можно показать, что если матрица А неособенная с ненулевыми диагональными элементами, то ее можно представить в виде произведения двух матриц где  — нижняя треугольная матрица с ненулевыми диагональными элементами; У вЂ” верхняя треугольная матрица с единичными диагональными элементами. Тогда решение уравнения можно свести к решению двух уравнений (5.5) где У - — вспомогательный вектор. Например, для системы из трех уравнений соотношения (5.4), (5.5) будут иметь вид (5.6) (5. 7) Сначала решаем уравнение (5.6) относительно У, а затем уравнение (5.7) относительно Х.
Матрицы 7, и (У треугольные, поэтому решение получается просто путем обратных подстановок. Очевидно, что алгоритм решения уравнения (5.6) можно организовать в виде циклического процесса вычисления из соотноше- ния о о 121 122 0 31 32 33 п12 13 ~23 0 1 ~:.1 Н "12 п13 21 22 п23 31 132 УЗЗ (5.10) Согласно методу Краута элементы этой матрицы должны вычисляться в следующем порядке (1) (4) (7 (2) (5) (8) (3) (6) (9) Из соотношения (5.1) следует, что произведение матрицы Ь на У дает матрицу А, элементы которой известны. Поэтому используя правило умножения матриц можно записать систему соотношений„связывающих элементы матриц Ь, (У и А.
Эти соотношения можно разрешить относительно (у и иу .. Метод Краута устанавливает такой порядок вычисления элементов матриц Е и (У, чтобы все эти соотношения были записаны в явной форме. Пусть имеем систему из трех уравнений. Введем условно матрицу Н вида (5. 8) у =, у=1,2,...,п у,у У вЂ” 1 где я=~ (уь уу,. Ус = 1 Решение уравнения (5.7) также можно организовать в виде циклического процесса, но в обратном порядке.
Значения переменных х вычисляются нз соотношения: х.=у.— Я, у=п, п — 1, ...„1, у у и где Я = ~~у Еууу, х, . Уу .—. у + 1 Для разложения матрицы А на матрицы Х и (У можно разработать различные алгоритмы, в частности, можно использовать метод Краута, позволяющий определить элементы матриц 7. и (У рекурсивно, без запоминания промежуточных результатов.
где (уу) показывает, что вычисляется уу-й элемент. Т.е. сначала вычисляются элементы первого столбца, затем элементы первой строки. Далее в оставшейся части снова вычисляются элементы первого столбца и элементы первой строки и так далее. Из полученной матрицы Н легко сформировать матрицы Е и (У. Алгоритм Краута можно сформулировать в виде следующей последовательности шагов (А и Н вЂ” матрицы размером уп х т): 1) получим первый столбец Н путем вычисления Н =Аз для Уу=1,2,..., уп; 2) заполним первую строку матрицы Н путем вычисления Ауу, Ньь=Н ' для Уу=8,-, иу; 11' 3) положим у = 2.„ 4) заполним содержимое у-го столбца Н, вычисляя Н .
=А -— ЗУ Лу НЫ з Н1у.— НЬ2* Нзу ...НЬ Ьу Ы зН( 1) ДлЯ УУ=У)У+1, ...,Уп; 5) если у = т, закончим алгоритм, иначе перейдем к шагу 6; 5.3. Метод простой итерации ")г "2 11)З хЗ )= а Ьг — аг) х) — агз хз пгг (5.11) "З ОЗ) Хт Огг Хг х = азз Х=ТХ+С.
есть )) Т)) = шах ~~> Е,.а . (5.13) М)ь) = шах ~х( ) — х( )~ с е, 1 1 (5. 12) 6) заполним у-ю строку Н путем вычисления Н . = (А „— й 1' Дь — 1) ' 6-))ь Н2 Нга )т 12 Н- Ё й = ) +1„) +2, ..., ги; 7) положим ) =) + 1и перейдем к шагу 4. Таким образом алгоритм решения ЛАУ методом ь()-разложения в общем случае должен включать в себя следующие функции: перестановку строк матрицы А, если в ней есть нулевые диагональные элементы; формирование матриц 7.
и с); решение уравнения (5.4) в соответствии с соотношением (5.8); решение уравнения (5.5) в соответствии с (5.9). Для решения системы уравнений (5.1) методом простой итерации запишем уравнения в виде Суть метода простой итерации заключается в следующем. Выберем начальные приближения для переменных х), хг, хз и подставим их в правые части уравнений (5.11). В результате вычислений получим первое приближение значений переменных (х, хг, хз ). Эти значения подставим в правые части (5.11) и вычислим второе приближение.
Этот процесс будем продолжать до тех пор пока не выполнится условие где ))4( ) — погрешность решения уравнений; 1 — номер переменной; Й вЂ” номер итерации; с — заданная погрешность. Из уравнений (5.11) видно, что коэффициенты а)) должны быть отличны от нуля. Обычно накладывают более жесткое требование — диагональные элементы матрицы А должны иметь максимальные значения. Алгоритм решения системы линейных уравнений методом простой итерации можно сформулировать следующим образом.
1. Переставляем столбцы в матрице А и строки в уравнениях так, чтобы коэффициенты а.. имели максимальные значения. и 2. Задаем начальные приближения для переменных (массив Х). 3. В цикле, используя расчетную формулу Ь, — п)1 Х) — з)2 Хг — .зз1.; 1 Х) 1 — з1) 1+) Х1з) " о1гз Хп ХК;= ' л вычисляем очередное приближение (массив ХК). (д) 4. В цикле определяем максимальную погрешность 1и 5.
Присваиваем элементам массива Х значения соответствующих элементов массива ХК. 6. Сравниваем 1)4~ ') с заданной погрешностью. Процесс продолжаем до тех пор, пока не вьшолнится условие (5.12). Сходимость вычислительного процесса зависит от соотношения коэффициентов в уравнениях. Уравнения (5.11) в матричной Форме можно записать в виде Можно показать, что метод простой итерации сходится если норма матрицы Т с 1.
Норма матрицы Т вычисляется как максимальное значение из суммы модулей элементов строк матрицы, то 5.4. Метод Гаусса — Зейделя ПРИЛОЖЕНИЕ Метод Гаусса — Зейделя подобен методу простой итерации и отличается от него только тем, что значения х( вычисленные на 1й+ Ц ) итерации ()с + 1) сразу же на этой итерации используются при вычислении х +, х.+2, ..., хп .
Это означает, что итеРаЦион(и+ ц )и+ ц (и+ ц )+ ный процесс применяется к системе вида и и и+ 1 Ь1 — п12 хг — п13 хз х 1 а йе1 и и+1 Ьг "21 х1 агз хз 2 "22 А+1 йь1 1 Ьз — пз1 х1 пз2 х2 3 "33 Алгоритм решения уравнений методом Гаусса Зейделя автоматически получается из алгоритма метода простой итерации если исключить массив ХК и вычисленные значения переменных заносить в массив Х. Замечание.
В данном случае значения переменных с предыдущей итерации не сохраняются, поэтому нельзя определить погрешность решения как разносгь значений соответствующих элементов массивов переменных с соседних итераций (как в методе простой итерации„соотношение (5.12)). Погрешность решения конско определить в самом цикле решения уравнений, еычиеляя ее до занесения значений переменных в массив Х.
Правила оформления пояснительной записки Пояснительная записка оформляется в соответствии с требованиями единой системы программной документации. Листы формата А4 пояснительной записки, кроме титульного, должны иметь сквозную нумерацию (на верхнем поле в центре листа). Листы должны быть сброшюрованы в обложке из плотной бумаги. Пояснительная записка должна содержать титульный лист; содержание; задание по курсовой работе; анализ задания и обоснование методов решения задачи; описание применяемых численных методов; список обозначений в алгоритмах и программе; схемы алгоритмов программы и подпрограмм и их описание„ набор тестов для отладки программ; распечатка текста программы и ее описание," инструкция по использованию программы; анализ результатов решения задачи; выводы; список источников, использованных при разработке программы.
Содержание пояснительной записки размещают на отдельной странице (пронумерованной), снабженной заголовком "Содержание". В содержание включают номера разделов и подразделов, имеющих заголовок, их наименования и номера страниц. Наименования, включенные в содержание, записывают строчными буквами. Прописными записываются только заглавные буквы и аббревиатуры. Задание по курсовой работе оформляется на отдельном листе и подписывается курирующим преподавателем и студентом, принявшим задание к исполнению. Задание по курсовой работе явля~ тся отчетным документом, без которого пояснительная записка пя проверку не принимается, а работа к защите не допускается. Текст пояснительной записки разбивают на разделы, подразделы и пункты, которые, в свою очередь, могут быть разбиты на подпункты.
Раздел — первая ступень деления текста, обозначенная номером и снабженная заголовком. Подраздел — часть раздела, обозначенная номером и имеющая заголовок. Нумерации подраздела состоит из номера раздела и номера подраздела, разделенных точкой ( например, 2.4 — четвертый подраздел второго раздела ). Пункт — часть подраздела, обозначенная номером и снабженная заголовком.
Нумерация пункта состоит из номера раздела, номера подраздела и номера пункта, разделенных точкой. Внутри подразделов, пунктов и подпунктов могут быть перечисления, которые обозначаются арабскими цифрами со скобкой, например 1), 2), и так далее. Не рекомендуется делать ссылки на перечисления. Заголовки разделов пишутся прописными буквами и размещаются симметрично относительно правой и левой границ текста. Точку в конце заголовка не ставят, переносы слов в заголовках не допускаются. Каждый раздел рекомендуется начинать с нового листа. Расстояние между заголовком и последующим текстом должно быть равно: при выполнении документа ручным способом — 10 мм; при выполнении машинописным способом — полутора интервалам. Текст пояснительной записки должен быть кратким, четким, исключающим возможность неоднозначного толкования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
