Пусть дана система линейных алгебраических уравнений с n неизвестными: a 11 x 1 + a 12 x 2 + … + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n = b. - презентация

1

2 Пусть дана система линейных алгебраических уравнений с n неизвестными: a 11 x 1 + a 12 x 2 + … + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n = b 2 a n1 x 1 + a n2 x 2 + … + a nn x n = b n … Обозначим: a 11 a 12 … a 1n a 21 a 22 … a 2n … a n1 a n2 … a nn A = x1x2…xnx1x2…xn X = b1b2…bnb1b2…bn B = матрица коэффициентовстолбец свободных членов столбец неизвестных Тогда можно записатьAX = B

3 Шаг 1 Получение расширенной матрицы - добавим к основной матрице A столбец свободных членов B a 11 a 12 … a 1n a 21 a 22 … a 2n … a n1 a n2 … a nn A = b1b2…bnb1b2…bn Фрагмент блок-схемы

4 Шаг 2 Прямой ход метода Гаусса - приведение расширенной матрицы к треугольному виду a 11 a 12 a 13 … a 1n-1 a 1n 0 a 22 a 23 … a 2n-1 a 2n 0 0 a 33 … a 3n-1 a 3n … … 0 a nn A = b1b2b3…bnb1b2b3…bn Как это сделать?

5 а. Формирование первого столбца матрицы a 11 a 12 … a 1n b 1 a 21 a 22 … a 2n b 2 a n1 a n2 … a nn b n … a 31 a 32 … a 3n b 3 M = a 11 a 21 a 11 a 12 … a 1n b 1 a 22 … a 2n b 2 a n2 … a nn b n … a 32 … a 3n b 3 a 21 =a 21 -M. a 11 =0; a 22 =a 22 -M. a 12 ; … M = a 11 a 31 a 31 =a 31 -M. a 11 =0; a 32 =a 32 -M. a 12 ; … M = a 11 a n1 a n1 =a n1 -M. a 11 =0; a n2 =a n2 -M. a 12 ; … б. Формирование второго столбца матрицы a 11 a 12 … a 1n b 1 0 a 22 … a 2n b 2 0 a n2 … a nn b n … 0 a 32 … a 3n b 3 a 11 a 12 … a 1n b 1 0 a 22 … a 2n b 2 … a nn b n … … a 3n b 3 M = a 22 a 32 a 32 =a 32 -M. a 22 =0; a 33 =a 33 -M. a 23 ; … M = a 22 an2an2 a n2 =a n2 -M. a 22 =0; a n3 =a n3 -M. a 23 ; … И т.д. до n-го столбца: a ij = a ij – M. a kj M = a kk a ik ; Но возникает вопрос …

6 Если на главной диагонали встретится нулевой элемент, то рассчитать коэффициент M будет невозможно (делить на ноль нельзя) Перед обнулением элементов в k-том столбце среди элементов, лежащих ниже диагонального, найти максимальный по модулю, запомнить номер строки, в котором он находится, и поменять эту строку с k-той строкой местами. Например, a 11 a 12 … a 1n b … a 2n b 2 0 a n2 … a nn b n … 0 a 32 … a 3n b 3 Допустим, среди элементов а 32 …а n2 максимальным является элемент 3-ей строки а 32 a 11 a 12 … a 1n b 1 0 a 22 … a 2n b 2 0 a n2 … a nn b n … 0 0 … a 3n b 3 Фрагмент блок-схемы

7 Шаг 3 Обратный ход метода Гаусса -нахождение неизвестных После преобразований система уравнений имеет вид: a 11 x 1 + … + a 1 n-2 x n-2 + a 1 n-1 x n-1 + a 1 n x n = b 1 a n-2n-2 x n-2 + a n-2n-1 x n-1 + a n-2n x n = b n-2 a n-1n-1 x n-1 + a n-1n x n = b n-1 a nn x n = b n … Из последнего уравнения: Если a nn = 0, то x n = bnbn a nn ; если a nn = 0 и b n = 0, то x n-1 = b n-1 - a n-1n. x n a n-1n-1 ; x n-2 = b n-2 - a n-2n-1. x n-1 - a n-2n. x n a n-2n-2 ; … x i = b i - a ij. x j a ii Фрагмент блок-схемы система имеет бесконечное множество решений; система решений не имеет.

8 начало n i:=1,n j:=1,n a ij bibi Вернуться к описанию вводим размерность матрицы открываем внешний цикл по номеру строки открываем внутренний цикл по номеру столбца вводим значение элемента строки в качестве последнего элемента каждой строки вводим значение свободного члена

9 начало n i:=1,n j:=1,n a ij bibi Вернуться к описанию c:=b k b k :=b r b r :=c i:=k+1,n M:=a ik /a kk j:=1,n a ij :=a ij - Ma kj b i :=b i - Mb k если модуль текущего элемента больше max, то k:=1,n max:=|a kk | r:=k i:=k+1,n |a ik |>max max:=|a ik | r:=i j:=1,n c:=a kj a kj :=a rj a rj :=c открываем цикл по номеру столбца сохраняем в max модуль диагонального элемента текущей строки; в r запоминаем номер текущей строки внутренний цикл по номеру строки для просмотра элементов, лежащих ниже диагонального сохраняем его значение в max, а в r запоминаем номер текущей строки открываем цикл по номеру столбца меняем местами элементы текущей строки и строки, содержащей максимальный элемент открываем цикл по номерам строк, лежащих ниже диагонали находим коэффициент для текущей строки в цикле по номеру строки присваиваем элементам строки новые значения последним элементом строки является новое значение свободного члена a ij = a ij – M. a kj M = a kk a ik ;

10 начало n i:=1,n j:=1,n a ij bibi c:=b k b k :=b r b r :=c i:=k+1,n M:=a ik /a kk j:=1,n a ij :=a ij - Ma kj b i :=b i - Mb k k:=1,n max:=|a kk | r:=k i:=k+1,n |a ik |>max max:=|a ik | r:=i j:=1,n c:=a kj a kj :=a rj a rj :=c a nn =0 i:=n,1, -1 s:=0 j:=i+1, n s:=s + a ij x j x i :=(b i – s)/a ii xixi b n =0 конец Бесконечное мн-во решений Нет решений - + если последний элемент диагонали равен 0, то… если последний свободный член равен 0, то… иначе… иначе открываем обратный цикл по номеру строки обнуляем сумму цикл по номерам столбцов, лежащих правее диагонального элемента (для последней строки не выполняется) накапливаем сумму находим неизвестное в текущей строке выводим текущее неизвестное - 23 x i = b i - a ij. x j a ii

11 начало n i:=1,n j:=1,n a ij bibi k:=1,n max:=|a kk | r:=k i:=k+1,n |a ik |>max max:=|a ik | r:=i j:=1,n c:=a kj a kj :=a rj a rj :=c c:=b k b k :=b r b r :=c i:=k+1,n M:=a ik /a kk j:=1,n a ij :=a ij - Ma kj b i :=b i - Mb k a nn =0 i:=n,1, -1 s:=0 j:=i+1, n s:=s + a ij x j x i :=(b i – s)/a ii xixi b n =0 Бесконечное мн-во решений Нет решений конец программа

12 {обратный ход метода Гаусса} if a[n,n]=0 then if b[n]=0 then writeln ('Бесконечное множество решений') else writeln ('Нет решений') else for i:=n downto 1 do begin s:=0; for j:=i+1 to n do begin s:=s+a[i,j]*x[j]; end; x[i]:=(b[i]-s)/a[i,i]; writeln('x(',i,')=',x[i]:1:2); end; end. program slau; var a: array[1..100,1..100] of real; x,b: array[1..3]of real; r,i,j,k,n: integer; max,c,m,s:real; begin {ввод элементов массива} write (Введите размерность'); read (n); for i:=1 to n do begin for j:=1 to n do begin write ('a[',i,',',j,']='); read (a[i,j]); end; writeln; write ('b[',i,']='); readln(b[i]); end; {прямой ход метода Гаусса} for k:=1 to n do begin max:=abs(a[k,k]); r:=k; for i:=k+1 to n do if abs(a[i,k])>max then begin max:=abs(a[i,k]); r:=i; end; for j:=1 to n do begin c:=a[k,j]; a[k,j]:=a[r,j]; a[r,j]:=c; end; c:=b[k]; b[k]:=b[r]; b[r]:=c; for i:=k+1 to n do begin m:=a[i,k]/a[k,k]; for j:=k to n do a[i,j]:=a[i,j]-m*a[k,j]; b[i]:=b[i]-m*b[k]; end; end; {вывод треугольной матрицы} for i:=1 to n do begin for j:=1 to n do write(a[i,j]:1:2,' '); writeln(b[i]:1:2); end;