Лекция №4 Прямые методы решения слау пусть дана система n линейных уравнений с n неизвестными Ax=b 1) Где a матрица X вектор неизвес - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Решение систем трех линейных уравнений. Матрицы и действия над ними 1 48.28kb.
Решение систем трех линейных уравнений. Матрицы и действия над ними 1 78.37kb.
004. 896, 519. 612. 2, 004. 514. Бегляров В. В 1 58.71kb.
Программа итогового государственного экзаменa по специальности 010600... 1 94.76kb.
Отчет по лр№1: «Решение систем линейных алгебраических уравнений... 1 64.28kb.
Лекция №2 (16. 02. 10) Определение 4 1 51.51kb.
Действия с линейными преобразованиями 1 36.51kb.
Задания для защиты контрольной работы n 1 1 52.28kb.
Решение произвольных систем уравнений. Совместные системы. Определенные... 1 252.62kb.
Определение линейного преобразования. Матрица линейного преобразования 1 30.27kb.
Iv. Численные методы решения обыкновенных дифференциальных уравнений. 1 78.46kb.
О возможности применения многомерной матричной алгебры к численному... 1 58.55kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Лекция №4 Прямые методы решения слау пусть дана система n линейных уравнений с n - страница №1/1

Лекция №4

Прямые методы решения СЛАУ

Пусть дана система n линейных уравнений с n неизвестными Ax=b (4.1)

Где A – матрица

x – вектор неизвестных

b – вектор свободных членов

Если единственное решение системы (4.1)

В самом деле, при обратная матрица A-1. Умножая обе части (4.1) на матрицу A-1 слева, получим

A-1 Ax= A-1b



x = A-1b (4.2)

Эта формула дает решение СЛАУ (4.1), причем единственное.




На экзамене:

Решить системы уравнений:

1)





2)








Решение системы вычисляется путем умножения обратной матрицы на столбец свободных членов. Из прошлой лекции: число операций для вычисления обратной матрицы: (4.3)

Поэтому формула (4.2) редко употребляется на практике.

Из этой формулы легко получить формулы Крамера:



(4.)

или


где (число!)

- определитель, полученный из определителя путем замены - го столбца столбцом свободных членов. (тоже число!) , если система имеет единственное решения, определяемое матричной формулой (4.2) или скалярными формулами (4.4).

Подсчитаем количество арифметических операций при использовании формул (4.4): Для вычисления неизвестных необходимо найти значения определителя. Если мы будем вычислять определители матриц без использования экономичных формул, то получим



(4.5)

Домашнее задание

Распишите формулы Крамера для системы 2-ч уравнений с 2-мя неизвестными.

Поэтому методы решения СЛАУ с использованием обратной матрицы или по формулам Крамера непригодны для практического решения при больших значениях из-за большого объема вычислений.

Наиболее распространенными из прямых методов являются метод исключения Гаусса и его модификации.

Рассмотрим применение метода исключения для:



  • решения СЛАУ;

  • вычисления определителя;

  • нахождения обратной матрицы.

Метод Гаусса можно интерпретировать как метод, в котором первоначальная матрица приводится к верхней треугольной форме (прямой ход), потом – к единичной (обратной ход). Очевидно, что если матрица единичная то .

Итак, метод основан на приведении матрицы системы к виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью 1-ого уравнения исключается из всех последних уравнений системы. Потом с помощью 2-ого уравнения исключается из 3-ого и всех последних уравнений.

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

Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных: решая последнее уравнение, находим - единственное в этом уравнении неизвестное. Далее используя это значение, из предыдущего уравнения вычисляем и т.д. Последним находим .

Важное замечание: описанные процедуры применимы лишь для систем с невырожденной матрицей. В противном случае (при условии, что вычисления проводятся точно) с помощью метода Гаусса можно ответить на вопрос, имеет ли система бесконечное множество решений или не имеет ни одного. Однако эти случаи мы рассматривать не будем.

Еще раз: мы предполагаем, что матрица невырожденная.

Рассмотрим применение метода Гаусса на примере системы из 3-х уравнений с 3-мя неизвестными.



(4.6)


Чтобы исключить из 2-го уравнения домножим 1-ое уравнение на - и прибавим ко 2-ому уравнению. Затем, домножим 1-ое уравнение на - и прибавим результат к 3-му уравнению, также исключив из него .

Получим систему, равносильную (4.6):





(4.7)


Где

Теперь из 3-го уравнения системы (4.7) необходимо исключить . Домножим 2-ое уравнение на и результат прибавим к 3-му уравнению.

Получим равносильную (4.7) систему:



(4.8)


Где

Матрица системы (4.8) имеет вид.

На этом заканчивается прямой ход метода Гаусса.

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



(4.9)

Используя это выражение, можно найти из 2-го уравнения, потом ил 1-го.



(4.10)

(4.11)

Аналогично строится вычислительный алгоритм для СЛАУ с произвольным числом уравнений.




Алгоритм см. у Турчак и Плотников «основы численных методов» стр. 116. рис. 4.2.


Ввод

Для от 1 / прямой ход метода Гаусса /



/ i - № неизвестного /


да



нет
/ к - № уравнения из n-го исключ. /


Перестановка уравнения


/ j - № столбца /



Для K от

Для от





До

До

До



Для от / обратный ход метода Гаусса /

/ i - № неизвестного, которое определяется для от из i-го уравнения /

/ j - № найденного неизвестного /

До



До 1 с шагом -1

Вывод

Одной из модификаций метода Гаусса является схема с выбором главного элемента. Здесь требование ( на диагональные элементы происходит деление в процессе исключения) заменяется более жестким: из всех оставшихся в i-м стобце элементов нужно выбрать наибольший по модулю и переставить уравнения так, чтобы этот элемент оказался на месте элемента .

А
Перестановка уравнения


лгоритм выбора главного элемента используется вместо при

с


мотри алгоритм.

Главные элементы можно выбирать либо по столбцу, либо по строке, либо по всей матрице.

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

Объем вычислений определятся порядком системы : число арифметических операций



(4.12)

Определитель и обратная матрица

Мы уже знаем, что вычисление определителя матрицы требует большого объема вычислений. Определитель матрицы вычисляется легко, он равен произведению ее диагональных элементов. Для приведения матрицы к виду можно использовать прямой ход метода Гаусса. В процессе исключения элементов величина определителя не меняется. Знак определителя меняется на противоположный при перестановке его столбцов или строк.

Следовательно, после приведения матрицы A к виду значение определителя вычисляется по формуле

(4.13)

Здесь - диаг. Элементы преобразованной матрицы.

К- число перестановок строк / столбцов матрицы.

Благодаря методы исключения можно вычислять определители и большего порядков. Объем вычислений значительно меньше, чем в (4.12).

Найдем обратную матрицу .

Обозначим ее элементы

Известно:




=





(4.14)

Где - столбец матрицы



- столбец матрицы (?? j место)

Следовательно, для нахождения j-го столбца обратной матрицы нужно решить систему уравнений (4.14). Необходимо решить таких систем для .

Мы найдем все столбцы и саму матрицу .

Поскольку при матрица системы (4.14) не меняется, исключение неизвестных при использовании метода Гаусса (прямой ход) проводится только один раз, причем сразу для всех правых частей – столбцов . Потом для каждой из систем (4.14) делается обратный ход с соответствующей преобразованной правой частью.

Оценки показывают, что это весьма экономичный способ обращений матрицы.

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



и невязкой
Пример: Решим СЛАУ методом Гаусса для случая трех уравнения:





(4.15)

Исключаем из второго и третьего уравнений. Первое умножим на 0.3 и результат прибавим ко второму, потом первое умножим на -0.5 и результат прибавим к третьему.






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








Прямой ход метода Гаусса закончен. Обратный ход асостоит в вычислении ,,.





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





(4.16)

Проведем исключение. Вычисления проведем в рамках арифметики с плавающей точкой, сохраняя 5 разрядов числа.

После первого шага исключения получим:






Следующий шаг проводим при малом ведущем элементе. Чтобы исключить из третьего уравнения, умножаем второе уравнение на 2500. При умножении имеем в правой части:



округление до 5 разрядов

В результате третье уравнение имеет вид:









Вычисления проводились с округлением до 5 разрядов по аналогии с процессом вычислений на компьютере. В результате получили решение вместо . Такая большая неточность результата объясняется малой величиной ведущего элемента.

Если переставить уравнения системы до исключения, получим систему:





Умножаем второе уравнение на и результат прибавляем к третьему:









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




Другие методы

Для систем с трех диагональной матрицей (частный случай разреженных систем) используют модификацию метода Гаусса – метод прогонки.

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

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

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



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




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