Метод Гаусса, LU-разложение. Прогонка для решения линейных систем с трехдиагональными матрицами коэффициентов. Метод квадратного корня для решения систем: краткая характеристика, теоретическая основа, реализация, тестирование и листинг программы.
Аннотация к работе
Три четверти прикладных математических задач в конечном итоге сводятся к решению систем алгебраических и трансцендентных уравнений, причем подавляющее большинство из них - линейные алгебраические системы, имеющие единственное решение. Современная вычислительная математика обладает большим арсеналом методов, а математическое обеспечение ЭВМ - многими пакетами прикладных программ, позволяющих решать различные линейные системы. Поэтому ввиду большой важности и практической значимости задача решения линейных систем до сих пор привлекает внимание математиков. Создано большое количество разных методов решения этой задачи и сопутствующих ей задач (вычисление определителей, обратных матриц). Среди этих методов можно выделить две большие группы: прямые (или точные) и итерационные методы [4].Совокупность коэффициентов (aij), неизвестных (хі) и свободных членов (bi) этой системы запишем в виде матриц [4]: A= , x= , b= (1.1.2) Помимо введенной матрицы А мы введем еще и расширенную матрицу системы, получающуюся из матрицы А добавлением столбца правых частей: (1.1.3) Для этого заменяем все уравнения, начиная со второго, уравнениями, полученными сложением каждого из них с первым, умноженным на -, -,…, -. Делим все элементы второй строки на , а затем исключаем переменную х2 из оставшихся строк путем опять же замены всех уравнений, начиная с третьего, уравнениями, полученными сложением каждого из них со вторым, умноженным на -, -,…, -. Коэффициенты данной системы получены по формулам [2]: , (i, j=k 1…n, k=1…n-1)Метод квадратного корня применяется в том случае, когда матрица А симметричная, то есть: aij = aji (i, j = 1, 2, …, n). Метод квадратного корня дает большой выигрыш во времени по сравнению с другими методами (например, методом Гаусса), так как, во-первых, существенно уменьшает число умножений и делений (почти в два раза для больших n), во-вторых, позволяет накапливать сумму произведений без записи промежуточных результатов. Всего метод квадратных корней требует [2,3] операций умножения и деления (примерно в два раза меньше, чем метод Гаусса), а также n операций извлечения корня. Запишем еще раз систему (1.1.1) n линейных алгебраических уравнений с n неизвестными [4]: Совокупность коэффициентов (aij), неизвестных (хі) и свободных членов (bi) этой системы запишем в виде матриц (1.1.2) [4]: A= , X= , B= К ee решению может быть применена идея разложения матрицы А в произведение двух матриц специального вида.В данной работе были рассмотрены прямые методы решения линейных систем: метод Гаусса, метод LU-разложения, метод прогонки, метод вращений и метод квадратного корня. К основным результатам курсовой работы можно отнести: обзор литературы, связанной с прямыми методами решения линейных систем.A, T: Massiv;{матрицы: исходная и матрица из разложения (2.3.1)} i, j, n: integer; {индексы} p, s, f: complex; {вспомогательные переменные} z: array [1..10] of real; {вспомогательный вектор-столбец} PROCEDURE SUM (a,b: complex; var c: complex); {процедуры SUM-KOR - это заранее BEGIN описанные математические операции, c.d :=a.d b.d; используемые в программе} c.y:=a.y b.y; KOR(A[1,1], T[1,1]); {нахождение 1 элемента по 1 формуле из (2.3.2)} for i:= 1 to n do {нахождение элементов1 строки и главной диагонали по 3 формуле из (2.3.2)} for j:=1 to n do if (i=j) and (ij) then begin s.d:= 0;{вспомогательные переменные} s.y:= 0; end else if i<j then {нахождение оставшихся элементов} begin s.
Введение
Три четверти прикладных математических задач в конечном итоге сводятся к решению систем алгебраических и трансцендентных уравнений, причем подавляющее большинство из них - линейные алгебраические системы, имеющие единственное решение.
Современная вычислительная математика обладает большим арсеналом методов, а математическое обеспечение ЭВМ - многими пакетами прикладных программ, позволяющих решать различные линейные системы. Казалось бы, этого достаточно, но на практике при решении линейных систем возникает множество разных проблем.
Поэтому ввиду большой важности и практической значимости задача решения линейных систем до сих пор привлекает внимание математиков. Создано большое количество разных методов решения этой задачи и сопутствующих ей задач (вычисление определителей, обратных матриц). Среди этих методов можно выделить две большие группы: прямые (или точные) и итерационные методы [4].
Прямые методы приводят к точному решению системы (если не учитывать вычислительные погрешности округлений), причем за конечное число шагов. К ним относятся методы Гаусса, LU-разложение, квадратного корня, методы прогонки, вращений и т.п. [2,4].
Итерационные методы позволяют получить приближенное решение системы с заданной точностью, используя идею последовательных приближений. К ним относятся методы простой итерации, Зейделя, релаксации, установления, спуска и т. п.[2,4].
Каждый из существующих методов решения линейных систем имеет свою сферу применения, где он является наиболее эффективным. Эффективность же названных численных методов зависит в основном от свойств матрицы системы (порядка, симметричности, меры обусловленности, заполненности).
Целью данной курсовой работы является: обзор литературы по прямым методам решения линейных систем;
реализация метода квадратного корня средствами системы программирования Turbo Pascal.
Курсовая работа содержит две главы. Первая глава посвящена таким прямым методам решения линейных систем, как метод Гаусса, LU-разложение, метод прогонки для решения линейных систем с трехдиагональными матрицами коэффициентов и метод вращений для решения линейных систем. Во второй главе отдельно рассматривается метод квадратного корня для решения линейных систем, а именно: приведены теоретические основы метода, а также произведена его реализация в системе программирования Turbo Pascal.
Вывод
В данной работе были рассмотрены прямые методы решения линейных систем: метод Гаусса, метод LU-разложения, метод прогонки, метод вращений и метод квадратного корня. К основным результатам курсовой работы можно отнести: обзор литературы, связанной с прямыми методами решения линейных систем.
Реализация метода квадратного корня средствами системы программирования Turbo Pascal.
Более подробно был проанализирован один из методов решения систем линейных алгебраических уравнений: метод квадратных корней. Метод был предложен для решения системы Ax=b, где матрица A - симметрическая.
Также в данной системе были проанализированы разного рода матрицы, и их влияние на точность полученного решения. Основываясь на полученных выводах, можно контролировать в каких конкретно моментах удобно решать систему линейных алгебраических уравнений методом квадратных, а когда лучше использовать другой метод.
2. Вержбицкий В.М. Основы численных методов. М.: Высшая школа. 2002.
3. Крылов В.И. и др. Вычислительные методы, т.I. М.: Наука, 1976.
4. Трубников С.В Численные методы. Часть 1: Теория погрешностей. Решение алгебраических и трансцендентных уравнений и систем: Учебное пособие для студентов вузов. - Брянск: Изд-во БГУ, 2005.
5. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М., Л.: изд-во физ.-мат. литры, 1963.