Сделай Сам Свою Работу на 5

Этап прямого хода закончен.





Тема 1. Численные методы алгебры

Лекция 2. Прямые и итерационные численные методы решения СЛАУ

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

 

Учебные вопросы:

2.1. Метод исключения Гаусса.

2.2. Метод простой итерации.

2.3. Метод Зейделя.

2.4.Метод скалярной прогонки ([1], с.26…28).

2.5. Сравнение прямых и итерационных численных методов решения СЛАУ.

 

Литература к лекции 2:

[1], с.16…34; [2], с.7…17,19…29; [3], с.4…13.

 

Метод исключения Гаусса.

Система линейных алгебраических уравнений (СЛАУ)общего вида в векторно-матричной форме записывается следующим образом

А Х = В, (*)

где А – квадратная матрица размером ;

Х = - вектор искомых параметров размером ;

В = - вектор правых частей размером .

 

Существование решения любой СЛАУ определяется условиями теоремы Кронекера-Капелли:

1). Для того чтобы СЛАУ (*) имела решение, необходимо и достаточно, чтобы ранг расширенной матрицы был равен рангу основной матрицы.

2). Если ранг основной и расширенной матриц совпадают с числом неизвестных, то СЛАУ (*) имеет единственное решение.



3). Если ранг r основной и расширенной матриц меньше числа неизвестных (r n), то СЛАУ (*) имеет более одного решения. В этом случае число «свободных» неизвестных, через которые выражаются остальные неизвестные, равно n-r.

Существуют различные модификации метода Гаусса – метод исключения, метод последовательной подставки и др. Наибольшее распространение получил метод исключения. Этот метод и будем изучать.

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

 

Дана СЛАУ:

a11·x1 + a12·x2 + a13·x3 = b1,

a21·x1 + a22·x2 + a23·x3 = b2,

a31·x1 + a32·x2 + a33·x3 = b3.

Прямой ход:

Составит расширенную матрицу:

x1 x2 x3 b
a11 a12a13 b1
а21 a31 a22 a23 a32 a33 b2 b3

 

Первый шаг -a21/ a11; -a31/ a11 a11≠ 0! =b2+b1·(-a21/ a11) =b3+b1·(-a31/ a11)

 

матрица системы А



 

a11 a12a13 b1
0
0

 

Второй шаг  

 

a11 a12 a13 b1
0
0

 

Прямой ход закончен Получили СЛАУ с треугольной матрицей

 

Обратный ход:

x3= ;

x2+ x3=

Обратный ход закончен!

Заданная СЛАУ решена методом исключения Гаусса.

Замечание 1. Если все элементы какой либо строки матрицы системы А в результате преобразования стали равными нулю, а правая часть b не равна нулю, то СЛАУ несовместна, поскольку не выполняются условия теоремы Кронеккера-Капели.

Замечание 2. Если элементы какой-либо строки матрицы системы А и правая часть (b) стали равными нулю, то СЛАУ совместна, но имеет бесконечное множество решений, которые получаются по методу Гаусса для СЛАУ порядка r, где r– ранг матрицы исходной СЛАУ.

 

Метод простой итерации

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

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

Рассмосрим метод простой итерации.

Имеем неоднородную СЛАУ, у которой det A ≠0

 

(1)

 

На основании теоремы Кронекера-Капелли СЛАУ (1) имеет единственное решение.

Для применения итерационных методов решения СЛАУ (1)- необходимо его привести к эквивалентному виду:

 

(2)

 

или в векторно-матрчной форме:



,

где ; ; . (3)

Приведение к эквивалентному виду может быть выполнено различными способами. Одним из наиболее распространенных является следующий.

а). Разрешим СЛАУ (1) относительно подчеркнутых неизвестных при ненулевых диагональных элементах aii≠0, i= .

 

б). Получим следующие выражения для компонентов вектора β и матрицы α эквивалентной системы:

(4)

Организуем итерационный процесс:

Нулевое или начальное приближение х(0) выбирается произвольно, но обычно его принимают равным β, тогда итерационную последовательность векторов вида:

 

(5)

 

называют методом простой итерации.

Возникает два вопроса:

1. Сходится ли последовательность векторов (5) к единственному решению СЛАУ?

2. Если сходится, то какова возникает ошибка в решении, если остановить итерационный процесс на (к+1)-ой итерации?

Ответ на первый вопрос дают две теоремы.

Теорема1. Достаточным условием сходимости метода простых итераций (5) к единственному решению СЛАУ (1) при любом начальном приближении является выполнение неравенства

(6)

для любой нормы матрицы эквивалентной системы (3)

 

Теорема 2.Для сходимости итерационного процесса (5) к единственному решению СЛАУ (1) при любом начальном приближении необходимо и достаточно, чтобы спектральный радиус матрицы был меньше единицы, т.е.

, (7)

где - спектральный радиус матрицы .

Ответ на 2-ой вопрос содержится в утверждении доказанном в работе [1]:

Утверждение: если выполняются условия теоремы (6) или теоремы (7) , то норма погрешности решения возникшей при остановке итерационного процесса на (к+1)-ой итерации будет оцениваться неравенством

(8)

где - точное решение СЛАУ (1) .

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

,

где - заданная ошибка решения СЛАУ (1).

 

Метод Зейделя

Метод простых итераций сходится, но иногда недостаточно быстро. Для ускорения существует метод Зейделя, заключающийся в том, что при вычислении элемента вектора неизвестных на (к+1)-ой итерации используется , , уже вычисленные на (к+1)-ой итерации. Значения остальных элементов , ,…, берутся из предыдушей итерации х(к). Так же как и в методе простых итераций строится эквивалентная СЛАУ (2) и за начальное приближение принимается вектор правых частей, т.е. х(0)=[ . Тогда метод Зейделя для известного вектора предыдущей итерации на (к+1)-ой итерации будет иметь вид:

 

(9)

к=0,1,2,3,… .

 

Из (9) следует, что

(10)

 

где В – нижняя треугодьная матрица с диагональными элементами равными нулю, так как ; С – верхняя треугольная матрица с диагональными элементами равными нулю, так как .

Из (10) получаем (Е – В) , (11)

 

(11)

 


 

Из(11) следует, что метод Зейделя является методом простой итерации с матрицей правой части и вектором правой части . Поэтому условия сходимости по аналогии имеют вид:

(12)

Ошибка решения , возникающая при остановке итерационного процесса на (К+1)-ой итерации не превышает величины

 

, (13)

 

где к+1 в правой части является показателем степени.

По аналогии с простой итерацией можно записать условие остановки итерационного процесса

- заданная ошибка решения СЛАУ.

 

Метод скалярной прогонки

Метод прогонки является эффективным методом решения СЛАУ с трехдиагональными матрицами, возникающими при конечно-разностной аппроксимации задач для ОДУ и одномерных уравнений в частных проихводных второго порядка, и является частным случаем метода Гаусса. По экономичности вычислений этот метод имеет существенное преимущество по сравнению с методом Гауса. Рассмотрим каноническую форму СЛАУ

, (*)

i= ,

где: - искомые переменные i-го уравнения;

- звдвнные коэффициенты i-го уравнения;

- заданная правая часть i-го уравнения.

Представим СЛАУ (*) в обычном виде

(14)

Решение СЛАУ или (*) будем искать в виде

 

(15)

 

где - прогоночные коэффициенты, подлежащие определению.

Метод скалярной прогонки состоит из двух этапов:

первый этаппрямой ход, где определяются коэффициенты и ;

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

xn→xn-1→xn-2→…→x2→x1.

Получим формулы, определяющие Ai,Bi, i= на прямом ходе.

Из первого уравнения в (14)имеем:

 

(16)

 

откуда ; , при i=1.

Из второго уравнения в (14) с заменой по формуле (16) получаем

 

,

 

где , .

 

Продолжая этот процесс, получим из i-го уравнения СЛАУ (14)

 

,

при .

 

Следовательно,

; , при .

Из последнего уравнения СЛАУ (14) имеем

 

, так как , при i=n;

т.е. .

Этап прямого хода закончен.

Этап обратного хода:

Из последнего уравнения имеем .

Далее обратный ход осуществляется в соответствии с формулой (15):

,

,

………

,

.

Этап обратного хода завершен.

Получено решение СЛАУ (14) методом скалярной прогонки.

Число операций в методе скалярной перегонки равно при n=20 равно 8n+1=161 операций

Число операций в методе Гауса равно .

По экономичности методов вывод ясен!

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.