Осуществление алгоритмов линейной алгебры

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

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

 

Достоинства метода

• Для матриц ограниченного размера  менее трудоёмкий по сравнению с  другими методами.

• Позволяет однозначно установить, совместна система или нет, и  если совместна, найти её решение.

• Позволяет найти максимальное число линейно независимых уравнений  — ранг матрицы системы.

Неоптимальность метода Гаусса. В 1969 году Штрассен доказал, что большие матрицы можно перемножить за время Θ(nlog2 7) = Θ(n2.81). Отсюда вытекает, что обращение матриц и решение СЛАУ можно осуществлять алгоритмами асимптотически более быстрыми, чем метод Гаусса. Таким образом, для больших СЛАУ метод Гаусса не оптимален по скорости.

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

Обра́тная ма́трица — такая матрица A⁻¹, при умножении на которую, исходная матрица A даёт в результате единичную матрицу E:

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

Ниже представлен пседокод программы  на Си, осуществляющей нахождение обратной матрицы.

1.  for (i=0; i<n; i++)
2.   for (j=0; j<n; j++)
3.    if (j==i) b[i][j]=1; else b[i][j]=0;
4.  for(s=0; s<n; s++){
5.   max=a[s][s];
6.   k=s;
7.   for (i=s; i<n; i++){
8.    if (abs(a[i][s])>max){
9.     max=abs(a[i][s]);
10.     k=i;
11.    }
12.   }
13.   if (a[k][s]<0) max=-max;
14.   if(max!=0){
15.    if (k!=s) {
16.     for (j=s; j<n; j++){
17.      c=a[s][j];
18.      a[s][j]=a[k][j]/max;
19.      a[k][j]=c; 
20.     }
21.     for (j=0; j<n; j++){
22.      m=b[s][j];
23.      b[s][j]=b[k][j]/max;   
24.      b[k][j]=m;
25.     }
26.    }else{
27.     for(j=s; j<n; j++){
28.      a[k][j]=a[k][j]/max; 
29.     }
30.     for (j=0; j<n; j++)
31.      b[k][j]=b[k][j]/max;
32.    }
33.   } else {
34.    printf ("matrica ne obratima\n");
35.    goto m10;
36.   }
37.  for (i=s+1; i<n; i++){
38.    c=a[i][s];
39.    for (j=s; j<n; j++)
40.     a[i][j]=a[i][j]-a[s][j]*c;
41.    for (j=0; j<n; j++)
42.     b[i][j]=b[i][j]-b[s][j]*c;
43.   } 
44.  }
45.  for (s=n-1; s>-1; s--)
46.   for (i=s-1; i>-1; i--)
47.    for (j=0; j<n; j++)
48.     b[i][j]=b[i][j]-a[i][s]*b[s][j];
49.  for (s=n-1; s>-1; s--){ 
50.   for (i=n-2; i>-1; i--){
51.    c=a[i][s];
52.    for (j=n-1; j>s; j--)
53.     a[i][j]=a[i][j]-a[s][j]*c;
54.    }
55.  }  
56.  for (i=0; i<n; i++){
57.   for(j=0;j<n; j++)
58.    printf("%f ", a[i][j]);
59.   printf ("\n");
60.  }
61.  printf ("\n");
62.  for (i=0; i<n; i++){
63.   for(j=0;j<n; j++)
64.    printf("%f ", b[i][j]);
65.   printf("\n");
66.  }
67. m10: return 0;
68. }

Описание: Алгоритм весьма прост. Изначально матрица В – единичная матрица. После приводим матрицу А к ступенчатому виду как было показано в программе Метод Гаусса, также делая соответствующие преобразования в матрице В. Далее находим элементы массива х.

 

5.Решение СЛАУ.

АХ=В; Х=А^-1В.

Приведем псевдо код программы  на Си.

1. for (i=0; i<n; i++)
2.   for (j=0; j<n; j++)
3.    if (j==i) b[i][j]=1; else b[i][j]=0;
4.  for(s=0; s<n; s++){
5.   max=a[s][s];
6.   k=s;
7.   for (i=s; i<n; i++){
8.    if (abs(a[i][s])>max){
9.     max=abs(a[i][s]);
10.     k=i;
11.    }
12.   }
13.   if (a[k][s]<0) max=-max;
14.   if(max!=0){
15.    if (k!=s) {
16.     for (j=s; j<n; j++){
17.      c=a[s][j];
18.      a[s][j]=a[k][j]/max;
19.      a[k][j]=c; 
20.     }
21.     for (j=0; j<n; j++){
22.      m=b[s][j];
23.      b[s][j]=b[k][j]/max;   
24.      b[k][j]=m;
25.     }
26.    }else{
27.     for(j=s; j<n; j++){
28.      a[k][j]=a[k][j]/max; 
29.     }
30.     for (j=0; j<n; j++)
31.      b[k][j]=b[k][j]/max;
32.    }
33.   } else {
34.    printf ("matrica ne obratima\n");
35.    goto m10;
36.   }
37.   for (i=s+1; i<n; i++){
38.    c=a[i][s];
39.    for (j=s; j<n; j++)
40.     a[i][j]=a[i][j]-a[s][j]*c;
41.    for (j=0; j<n; j++)
42.     b[i][j]=b[i][j]-b[s][j]*c;
43.   } 
44.  }
45.  for (s=n-1; s>-1; s--)
46.   for (i=s-1; i>-1; i--)
47.    for (j=0; j<n; j++)
48.     b[i][j]=b[i][j]-a[i][s]*b[s][j];
49.  for (s=n-1; s>-1; s--){ 
50.   for (i=n-2; i>-1; i--){
51.    c=a[i][s];
52.    for (j=n-1; j>s; j--)
53.     a[i][j]=a[i][j]-a[s][j]*c;
54.    }
55.  }  
56.  for (i=0; i<n; i++)
57.   for (j=0; j<h; j++)
58.    x[i][j]=0;
59.  for (k=0; k<n; k++)
60.   for (i=0; i<n; i++)
61.    for (j=0; j<h; j++)
62.     x[i][j]=x[i][j]+b[i][k]*d[k][j];
63.  for (i=0; i<n; i++){
64.   for(j=0;j<h; j++)
65.    printf("%f ", x[i][j]);
66.   printf ("\n");
67.  }
68.  printf ("\n");
69.  for (i=0; i<n; i++){
70.   for(j=0;j<n; j++)
71.    printf("%f ", b[i][j]);
72.   printf("\n");
73.  }

Описание: Сначала находим обратную матрицу к А, после умножаем ее на вектор В и находим вектор Х.

6. LU – разложение.

LU- разложение — представление матрицы A в виде произведения двух матриц, , где L—нижняя треугольная матрица, а U— верхняя треугольная матрица. LU-разложение еще называют LU-факторизацией.

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

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

1.

2.

Для

1.

2.

В итоге мы получим матрицы — L и U.

Вот псевдокод программы.

1.  for (i=0; i<n; i++)
2.   for (j=0; j<n; j++){
3.    l[i][j]=0;
4.    u[i][j]=0;
5.                       }
6.  for (i=0; i<n; i++)
7.   L[i][i]=1;
8.  for (j=0; j<n; j++)
9.   u[0][j]=a[0][j];
10.  for (j=1; j<n; j++)
11.   L[j][0]=a[j][0]/u[0][0];
12.  for (i=1; i<n; i++)
13.   for (j=i; j<n; j++){
14.    s=0;
15.    for (k=0; k<i-1; k++)
16.     s=s+l[i][k]*u[k][j];
17.    u[i][j]=a[i][j]-s;
18.                         }
19.  for (i=1; i<n; i++)
20.   for (j=i+1; j<n; j++){
21.    r=0; 
22.    for (k=0; k<i-1; k++)
23.     r=r+l[j][k]*u[k][i];
24.    l[j][i]=(a[j][i]-r)/u[i][i];
25.                       }

 

7. LUX=B.

Решение систем линейных уравнений. LU-разложение может быть использовано для решения системы линейных уравнений

где A— матрица коэффициентов системы, x— вектор неизвестных величин системы, b — вектор правых частей системы.

Если известно LU-разложение матрицы , , исходная система может быть записана как

Эта система может быть решена в  два шага. На первом шаге решается система

Поскольку L — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой.

На втором шаге решается система

Поскольку U — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.

Ниже предоставлен псевдокод программы.

1. for (i=0; i<n; i++)
2.   for (j=0; j<n; j++){
3.    l[i][j]=0;
4.    u[i][j]=0;
5.                       }
6.  for (i=0; i<n; i++)
7.   L[i][i]=1;
8.  for (j=0; j<n; j++)
9.   u[0][j]=a[0][j];
10.  for (j=1; j<n; j++)
11.   L[j][0]=a[j][0]/u[0][0];
12.  for (i=1; i<n; i++)
13.   for (j=i; j<n; j++){
14.    s=0;
15.    for (k=0; k<i-1; k++)
16.     s=s+l[i][k]*u[k][j];
17.    u[i][j]=a[i][j]-s;
18.                         }
19.  for (i=1; i<n; i++)
20.   for (j=i+1; j<n; j++){
21.    r=0; 
22.    for (k=0; k<i-1; k++)
23.     r=r+l[j][k]*u[k][i];
24.    l[j][i]=(a[j][i]-r)/u[i][i];
25.                       }
26.           for (i=0; i<n; i++){
27.   z=0;
28.   for(j=0; j<i-1; j++)
29.    z=z+l[i][j]*y[j][0];
30.   y[i][0]=b[i][0]-z;
31.  }
32.  for (i=0; i<n; i++){
33.   c=u[i][i];
34.   for (j=0; j<n; j++)
35.    u[i][j]=u[i][j]/c;
36.   y[i][0]=y[i][0]/c; 
37.  }
38.  for (i=0; i<n; i++){
39.   z=0;
40.   for(j=0; j<i-1; j++)
41.    z=z+u[i][j]*x[j][0];
42.   x[i][0]=y[i][0]-z;
43.  }

 

8. Применение метода Гаусса к  ленточно – диагональным матрицам.

Если матрица А имеет ленточно – диагональный вид, то программа  выглядит так:

1.  for (i=0; i<n; i++)
2.   for (j=0; j<n; j++)
3.    if ((i-j>k1)||(j-i>k2)) a[i][j]=0;
4.  for (s=0; s<n; s++){
5.   max=a[s][s];
6.   k=s;
7.   for (i=s; i<k1; i++){
8.    if (abs(a[i][s])>max){
9.     max=abs(a[i][j]);
10.     k=i;
11.    }
12.   }
13.   if (a[k][s]<0) max=-max;
14.   if(max!=0){
15.    if (k!=s) {
16.     for (j=s; j<k2; j++){
17.      c=a[s][j];
18.      a[s][j]=a[k][j]/max;
19.      a[k][j]=c; 
20.     }
21.     m=b[s];
22.     b[s]=b[k]/max;   
23.     b[k]=m;
24.     
25.    }else{
26.     for(j=s; j<k2; j++){
27.      a[k][j]=a[k][j]/max; 
28.     }
29.     b[k]=b[k]/max;
30.    }
31.   } else {
32.    printf ("mn-vo reshenii\n");
33.    goto m10;
34.   }
35.   for (i=s+1; i<n; i++){
36.    c=a[i][s];
37.    for(j=s; j<n; j++)
38.     a[i][j]=a[i][j]-a[s][j]*c;
39.     b[i]=b[i]-b[s]*c;
40.   }   
41.  }
42.  for (i=n-1; i>-1; i--){
43.   z=0;
44.   for(j=n-1; j>i-1; j--)
45.    z=z+a[i][j+1]*x[j+1];
46.   x[i]=b[i]-z;
47.   }

Как видно из программы, имея дополнительные сведения о  матрице А, можно написать программу, которая будет работать гораздо быстрее, чем программа  обычного Метода Гаусса.

 

 

 

 

Вывод:

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