Xreferat.com » Рефераты по математике » Численные методы

Численные методы

/> системи (16) одержується з вихідної матриці А шляхом множення А зліва на елементарну матрицю

(17)

так, що .При цьому систему (16) можна записати у вигляді

.

Матрицю (17) будемо називати елементарною трикутною матрицею, що відповідає першому кроку виключення методу Гаусса.

Перепишемо систему (16) у вигляді

,

, (18)

.

Здійснимо другий крок методу Гаусса, тобто виключимо невідому з останнього рівняння.

Тоді одержимо систему вигляду


,

, (19)

.


Можна переконатися,що перехід від (18) до (19) здійснюється завдяки множення системи (18) на елементарну трикутну матрицю

. (20)

Таким чином,після другого кроку виключення приходимо до системи

, (21)

де матриці і означені згідно (17), (20).

Нарешті, перемножаючи (21) на матрицю

одержимо систему

, (22)

матриця якої є верхньою трикутною матрицею з одиничною головною діагоналлю.

Звідки виходить, зокрема, що A=LU, де -нижня трикутна матриця.

Таким чином, -розклад матриці А може бути одержаний за допомогою елементарних трикутних матриць: спочатку будуються матриці та обчислюється , а потім відшукується .Відзначимо, що матриці мають простий вигляд

; ; ;

.

причому на діагоналі матриці містяться ведучі елементи методу виключення.

Запис методу Гаусса у вигляді (22) детально описує процес виключення.

Усе згадане раніш переноситься без винятку на системи рівнянь довільного порядку (2).

Процес виключення можна записати формулою

, (23)

де елементарна нижня трикутна матриця на к-му кроці виключення має вигляд

.

Матриця здійснює виключення невідомого з рівнянь з номерами к+1, к+2, ... ,m.

Матриці існують і мають вигляд

.


МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.


  1. Основная идея метода. Может оказаться, что система

Ax=f (1)

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

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

Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений

(2)

Предположим, что . Тогда на первом шаге будем исключать переменное . Такой прием эквивалентен тому, что си­стема (2) переписывается в виде

(3)

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

Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что . Перепишем систему (2) в виде


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

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

  1. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде

где -элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, необходимо рассмотреть матрицы перестановок.

ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квад­ратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.

ОПРЕДЕЛЕНИЕ 2. Элементарной матрицей перестановок на­зывается матрица, полученная из единичной матрицы перестановкой к-й и l-й строк.

Например, элементарными матрицами перестановок третьего по­рядка являются матрицы

Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения .

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

  2. Для любой квадратной матрицы А матрица отличается от А перестановкой к-й и l-й строк.

  3. Для любой квадратной матрицы А матрица отличается от А перестановкой к-го и l-го столбцов.

Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка:

(4)

Система имеет вид (1), где

(5)

Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому надо поменять местами вторую и первую строки и перейти к эквивалентной системе

(6)

Систему (6) можно записать в виде

(7)

т.е. она получается из системы (4) путем умножения на матрицу

пе­рестановок

Далее, к системе (6) надо применить первый шаг обычного метода ис­ключения Гаусса. Этот шаг эквивалентен умножению системы (7) на элементарную нижнюю треугольную матрицу

В результате от системы (7) перейдем к эквивалентной системе

(8)

или в развернутом виде

(9)

Из последних двух уравнений системы (9) надо теперь исключить перемен­ное . Поскольку максимальным элементом первого столбца уко­роченной системы

(10)

является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе

(11)

которую можно записать в матричном виде как

. (12)

Таким образом система (12) получена из (8) применением элемен-тар­ной матрицы перестановок

Далее к системе (11) надо применить второй шаг исключения обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную нижнюю треугольную матрицу

В результате получим систему

(13)

или

(14)

Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением

что эквивалентно умножению (13) на элементарную нижнюю треугольную мат­рицу

Таким образом, для рассмотренного примера процесс исключения Гаусса с вы­бором главного элемента по столбцу записывается в

виде

(15)

По построению матрица

(16)

является верхней треугольной матрицей с единичной главной диаго­налью.

Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (16) наряду с элементарными треугольными матри­цами могут присутствовать элементарные матрицы перестановок .

Покажем еще, что из (16) следует разложение

PA=LU, (17)

где L -нижняя треугольная матрица, имеющая обратную, P - матрица перестановок.

Для этого найдем матрицу

(18)

По свойству 2) матрица получается из матрицы переста­новкой второй и третьей строк,

Матрица согласно свойству 3) получается из

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: