Решение систем линейных уравнений Классы задач линейной алгебры - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Отчет по лр№1: «Решение систем линейных алгебраических уравнений... 1 64.28kb.
Решение систем трех линейных уравнений. Матрицы и действия над ними 1 78.37kb.
Решение систем трех линейных уравнений. Матрицы и действия над ними 1 48.28kb.
Лабораторная работа № Вариант №13. Решение систем линейных алгебраических... 1 66.4kb.
Программа курса "Линейная алгебра" 1 45.3kb.
Решение произвольных систем уравнений. Совместные системы. Определенные... 1 252.62kb.
Тематическое планирование по алгебре 7 класс ( при 3 уроках в неделю 1 85.48kb.
Учебная программа Дисциплины б9 «Методы математического моделирования» 1 193.05kb.
Вопросы к экзамену 1 семестра Множества. Подмножества. Основные определения 1 30.57kb.
Исследование системы линейных уравнений (неоднородной и однородной) 1 72kb.
О возможности применения многомерной матричной алгебры к численному... 1 58.55kb.
A тригономентичною формой записи комплексного числа b алгебраической... 1 64.32kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Решение систем линейных уравнений Классы задач линейной алгебры - страница №1/1

Численное решение систем линейных уравнений


Классы задач линейной алгебры

При численном решении большого круга задач в конечном итоге происходит их линеаризация, в связи с чем в соответствующих алгоритмах весьма широко используются методы линейной алгебры. В их числе:



  • решение систем линейных алгебраических уравнений (СЛАУ);

  • вычисление определителей матриц http://193.232.254.145/edu/meth_calc/files/07.files/image002.gif;

  • нахождение обратных матриц http://193.232.254.145/edu/meth_calc/files/07.files/image004.gif;

  • определение собственных значений и собственных векторов матриц http://193.232.254.145/edu/meth_calc/files/07.files/image006.gif

Постановка задачи решения СЛАУ: http://193.232.254.145/edu/meth_calc/files/07.files/image008.gif(1), где http://193.232.254.145/edu/meth_calc/files/07.files/image010.gif– квадратная матрица коэффициентов размерности n, http://193.232.254.145/edu/meth_calc/files/07.files/image012.gif– вектор неизвестных, http://193.232.254.145/edu/meth_calc/files/07.files/image014.gif– вектор свободных коэффициентов. Иногда СЛАУ представляют в виде расширенной матрицы http://193.232.254.145/edu/meth_calc/files/07.files/image015.gifразмерности n×(n+1), где в качестве последнего столбца фигурирует вектор свободных коэффициентов. В координатном представлении такая СЛАУ выглядит следующим образом:

http://193.232.254.145/edu/meth_calc/files/07.files/image017.gif(2)

Для решения СЛАУ применяют в основном два класса методов: прямые (выполняемые за заранее известное количество действий) и итерационные (обеспечивающие постепенную сходимость к корню уравнения, зависящую от многих факторов). Прямые методы обычно применяются для решения систем порядка n < 200, для бóльших n используются итерационные методы. Перед решением СЛАУ требуется проанализировать корректную постановку задачи:



  1. Если http://193.232.254.145/edu/meth_calc/files/07.files/image019.gif– решение существует и единственно. Если же определитель равен нулю, то тогда, если матрица вырождена (т.е. ее можно преобразовать к виду, когда как минимум одна строка коэффициентов – нули) решений бесконечное множество, иначе решения не существует.

  2. Если http://193.232.254.145/edu/meth_calc/files/07.files/image020.gifне имеет элементов с большими по модулю значениями – решение устойчиво (см. Пример к главе 1). Показателем плохо обусловленных систем является http://193.232.254.145/edu/meth_calc/files/07.files/image022.gif.

Алгоритм метода Гаусса

  1. Прямой ход.

Идея метода состоит в последовательном исключении неизвестных из системы n линейных уравнений. На примере первого уравнения системы (2) рассмотрим выражение для x1:

http://193.232.254.145/edu/meth_calc/files/07.files/image024.gif.

Подставим выражение для x1 во второе и все остальные уравнения системы:



http://193.232.254.145/edu/meth_calc/files/07.files/image026.gif.

Для расширенной матрицы коэффициентов это означает, что каждый элемент первой строки следует поделить на диагональный элемент, а все остальные строки преобразовать, как показано выше. Таким образом, станут равны нулю все коэффициенты первого столбца, лежащие ниже главной диагонали. Затем аналогичная процедура проводится со второй строкой матрицы и нижележащими строками, при этом первая строка и первый столбец уже не изменяются. И так далее до тех пор, пока все коэффициенты, лежащие ниже главной диагонали, не будут равны нулю.

Общие формулы прямого хода:

akj*=akjakk, (3)



k = 1…n, j = 1…n+1. Звездочкой отмечены элементы k-й строки с измененными значениями, которые будут подставлены в следующую формулу. Для определенности будем считать первый индекс – по строкам, второй – по столбцам.

http://193.232.254.145/edu/meth_calc/files/07.files/image030.gif, (4)

i = k+1…n, j = 1…n+1, k фиксировано в уравнении (3). Для уменьшения количества действий достаточно изменять значения элементов, находящихся выше главной диагонали.

  1. Обратный ход.

Второй этап решения СЛАУ методом Гаусса называется обратным ходом и состоит в последовательном определении xk, начиная с xn, так как для последнего решение фактически получено. Общая формула:

http://193.232.254.145/edu/meth_calc/files/07.files/image032.gif. (5)

Таким образом, вычисление корней http://193.232.254.145/edu/meth_calc/files/07.files/image033.gifпроисходит за 2/3 n3 арифметических действий.



  1. Выбор главного элемента.

Для уменьшения погрешности вычислений следует стремиться к тому, чтобы на главной диагонали матрицы стояли максимальные по модулю значения коэффициентов. Алгоритмически этого можно добиться, переставляя строки таким образом, чтобы на диагонали стоял наибольший по модулю элемент текущего столбца. Такая процедура называется выбором главного элемента и осуществляется всякий раз при переходе к новой строке в прямом цикле метода Гаусса.

  1. Погрешность метода. Расчет невязок.

Точность результатов будет определяться только точностью выполнения арифметических операций при преобразовании элементов матрицы, т.е. ошибкой округления. Контроль правильности полученного решения осуществляется подстановкой полученных значений x1xn в исходную систему уравнений и вычислением невязок, т.е. разностей между правыми и левыми частями уравнений:

http://193.232.254.145/edu/meth_calc/files/07.files/image035.gif, где k = 1…n. (6)

Специально отметим, что подставлять найденные значения http://193.232.254.145/edu/meth_calc/files/07.files/image036.gifследует в исходную (не преобразованную к верхнетреугольному виду) систему.



  1. Преимущества и недостатки метода.

Преимущество метода в том, что он позволяет достичь результата за заранее известное и фиксированное число действий. Точность результатов будет определяться правильным выбором порядка коэффициентов в матрице http://193.232.254.145/edu/meth_calc/files/07.files/image037.gifи ее размерностью. Недостатком метода является резкое увеличение времени и погрешности вычислений с ростом n.

Блок-схема алгоритма метода Гаусса без выбора главного элементаhttp://193.232.254.145/edu/meth_calc/files/gauss.files/image001.gif


Итерационные методы решения систем линейных уравнений.

Простейшим итерационным методом решения СЛАУ является метод простой итерации. При этом система уравнений http://193.232.254.145/edu/meth_calc/files/07.files/image039.gif(1) преобразуется к виду http://193.232.254.145/edu/meth_calc/files/07.files/image041.gif(2), а ее решение находится как предел последовательности http://193.232.254.145/edu/meth_calc/files/07.files/image043.gif(3), где {n} – номер итерации. Утверждается, что всякая система (2), эквивалентная (1), записывается в виде http://193.232.254.145/edu/meth_calc/files/07.files/image045.gif.

Теорема о достаточном условии сходимости метода простой итерации утверждает, что если норма матрицы http://193.232.254.145/edu/meth_calc/files/07.files/image047.gif( http://193.232.254.145/edu/meth_calc/files/07.files/image049.gif), то система уравнений (2) имеет единственное решение и итерационный процесс (3) сходится к решению со скоростью геометрической прогрессии.

Теорема о необходимом и достаточном условии сходимости метода простой итерации: Пусть система (2) имеет единственное решение. Итерационный процесс (3) сходится к решению системы (2) при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы http://193.232.254.145/edu/meth_calc/files/07.files/image051.gifпо модулю меньше 1.

На практике для обеспечения сходимости итерационных методов необходимо, чтобы значения диагональных элементов матрицы СЛАУ были преобладающими по абсолютной величине по сравнению с другими элементами.

Представим СЛАУ в следующей форме, удовлетворяющей (3):

http://193.232.254.145/edu/meth_calc/files/07.files/image053.gif(4)

Зададим начальные приближения http://193.232.254.145/edu/meth_calc/files/07.files/image055.gifи вычислим правую часть (4), получим новые приближения http://193.232.254.145/edu/meth_calc/files/07.files/image057.gif, которые опять подставим в систему (4). Таким образом организуется итерационный процесс, который обрывается по условию http://193.232.254.145/edu/meth_calc/files/07.files/image059.gif, где http://193.232.254.145/edu/meth_calc/files/07.files/image061.gif– заданная погрешность.

К ускорению сходимости приводит использование приближения к решениям путем последовательного уточнения компонентов, причем k-я неизвестная находится из k-го уравнения. Такая модификация итерационного метода носит название метода Зейделя:

http://193.232.254.145/edu/meth_calc/files/07.files/image063.gif

Критерий сходимости метода Зейделя: Пусть http://193.232.254.145/edu/meth_calc/files/07.files/image065.gif– вещественная симметричная положительно определенная матрица. Тогда метод Зейделя сходится.

Достоинствами метода простых итераций является простота программной реализации и более быстрый, по сравнению с линейными методами, поиск решения в матрицах большого размера. Недостатками являются сложный контроль условий сходимости и выбора начального приближения.



Решение систем линейных уравнений в среде MathCAD

В матричной форме СЛАУ записывается в эквивалентном виде:


http://193.232.254.145/edu/meth_calc/files/mathcad.files/image010.gif, где http://193.232.254.145/edu/meth_calc/files/mathcad.files/image012.gif— матрица коэффициентов СЛАУ размером n*n, http://193.232.254.145/edu/meth_calc/files/mathcad.files/image014.gif- вектор неизвестных,
http://193.232.254.145/edu/meth_calc/files/mathcad.files/image016.gif— вектор правых частей уравнений.

В Mathcad СЛАУ можно решить как в более наглядной форме, так и в более удобной для записи. Для первого способа следует использовать вычислительный Given/Find, а для второго — встроенную функцию Isolve.

Isolve (A,b) — решение системы линейных уравнений, где: А — матрица коэффициентов системы; вектор правых частей.

Примеры:


Метод обратной матрицы

http://193.232.254.145/edu/meth_calc/files/mathcad.files/image018.jpg

Используя функцию Isolve:



http://193.232.254.145/edu/meth_calc/files/mathcad.files/image020.jpg

Используя вычислительный Given/Find:



http://193.232.254.145/edu/meth_calc/files/mathcad.files/image022.jpg
Решение системы линейных алгебраических уравнений с помощью функций lsolve, Find и rref

http://twt.mpei.ac.ru/ochkov/mathcad_14/chapter3rus/3-17-singular.png

Одна из ошибок при решении системы линейных алгебраических уравнений — неправильное вычисление обратной матрицы



http://twt.mpei.ac.ru/ochkov/mathcad_14/chapter3rus/3-18-singulag-check.png

Графическая иллюстрация множества корней системы трех линейных алгебраических уравнений



http://twt.mpei.ac.ru/ochkov/mathcad_14/chapter3rus/3-19-book.png
Решение системы линейных алгебраических уравнений с помощью оператора solve

http://twt.mpei.ac.ru/ochkov/mathcad_14/chapter3rus/3-20-singular-solve.png

Инструменты настройки Mathcad-функции Find



http://twt.mpei.ac.ru/ochkov/mathcad_14/chapter3rus/3-21-par-solver-mathcad.png
Решение недоопределенных и переопределенных уравнений

http://twt.mpei.ac.ru/ochkov/mathcad_14/chapter3rus/3-22-lsolve-mathcad-13.png