ПЯВУ. Основы программирования. Лекция 14. Решение системы уравнений методом Гаусса. Вычисление числа Пи методом “МонтеКарло”

Сентябрь 7, 2022

Главная
Алгебра
ПЯВУ. Основы программирования. Лекция 14. Решение системы уравнений методом Гаусса. Вычисление числа Пи методом “МонтеКарло”

Содержание

2. Контрольные вопросы Почему в C# рекомендуют использовать свойства вместо полей данных? Что такое рекурсия? В чем
3. План лекции Решение системы уравнений методом Гаусса Вариант с выбором ведущего элемента Вычисление детерминанта методом Гаусса
4. Системы линейных уравнений и Матрицы a11*x1 + a12*x2 + … a1N*xN = b1 a21*x1 + a22*x2
5. Метод Гаусса a’11*x1 + a’12*x2 + … a’1N*xN = b’1 a’22*x2 + … a’2N*xN = b’2
6. Представление системы уравнений Матрицу представим в виде двумерного массива: double [,] M = new double[N, N+1];
7. Алгоритм вычитания строк Здесь k – номер строки, которую надо вычитать … static void SubtractRow(double [,]
8. Приведение матрицы к верхнетреугольному виду static void TriangleMatrix(double [,] M) { for(int i = 1; i
9. Решение Последнее уравнение содержит только 1 неизвестное – xN. После решения последнего уравнения, можно решить предпоследнее,
10. “Слабые” места SubtractRow: double m = M[k, k]; … M[i, j] = M[i, j] - M[k,
11. Улучшение метода Выбор “ведущего элемента”. Идея заключается в том, что бы каждый раз выбирать из оставшихся
12. Выбор ведущего элемента //Находит строку, в которой элемент n имеет наибольшее по модулю значение, // и
13. Усовершенствованная триангуляция матрицы static void TriangleMatrix(double [,] M) { for(int i = 1; i { SelectLeading(M,
14. Решение есть не всегда static bool TriangleMatrix(double [,] M) { for(int i = 1; i {
15. Решение public static double [] Solve(double [,] M) { if(!TriangleMatrix(M)) retun null; double v[] = new
16. Решение double[,] M = new double[4, 5] { { 2, 3, 1, 1, 1 }, {
17. Детерминант и метод Гаусса Если не применять выбор ведущего элемента, то детерминант – это просто произведение
18. Выбор ведущего элемента static bool SelectLeading(double [,] M, int n) { //Найдем номер строки, с наибольшим
19. Вычисляем детерминант static double Determinant(double [,] M) { double d = 1; for(int i = 1;
20. Контрольные вопросы Как в решении задачи проявился характер вычислений с числами с плавающей точкой? Какие преобразования
21. Вычисление числа Пи методом “Монте-Карло” Метод основан на применении для вычислений случайных чисел. Если моделировать попадание
22. Вычисление числа Пи Sокр = Пи*R2 Удобно взять R = 1 и ограничиться 1-ой четвертью математической
23. Вычисление Пи Реализация int N=1000000; int n=0; Double x, y; Random r = new Random(); for(int
25. Скачать презентацию

Слайд 2

Контрольные вопросы
Почему в C# рекомендуют использовать свойства вместо полей данных?
Что такое

рекурсия?
В чем заключается метод Гаусса решения системы линейных уравнений?
Какие варианты решения системы уравнений могут быть?

Слайд 3

План лекции
Решение системы уравнений методом Гаусса
Вариант с выбором ведущего элемента
Вычисление детерминанта

методом Гаусса
Вычисление числа Пи методом “Монте-Карло”.

Слайд 4

Системы линейных уравнений и Матрицы
a11x1 + a12x2 + … a1N*xN =

b1
a21*x1 + a22*x2 + … a2N*xN = b2
…
aN1*x1 + aN2*x2 + … aNN*xN = bN
В векторном виде:
A*x = b
x = {x1, x2 , … xN}

Слайд 5

Метод Гаусса
a’11x1 + a’12x2 + … a’1NxN = b’1
a’22x2 +

… a’2N*xN = b’2
…
a’NN*xN = b’N

Слайд 6

Представление системы уравнений
Матрицу представим в виде двумерного массива:
double [,] M =

new double[N, N+1];
Число строк матрицы N. Число столбцов N + 1, т.к. включает и свободный вектор b.
…
Заполняем матрицу коэффициентами…

Слайд 7

Алгоритм вычитания строк
Здесь k – номер строки, которую надо вычитать …
static

void SubtractRow(double [,] M, int k)
{
double m = M[k, k];
for(int i = k+1; i < M.GetLength(0); i++)
{
double t = M[i, k]/m;
for(int j = k; j < M.GetLength(1); j++)
{
M[i, j] = M[i, j] - M[k, j]*t;
}
}
}

Слайд 8

Приведение матрицы к верхнетреугольному виду
static void TriangleMatrix(double [,] M)
{
for(int i =

1; i < M.GetLength(0); i++)
SubtractRow(M, i-1);
}

Слайд 9

Решение
Последнее уравнение содержит только 1 неизвестное – xN. После решения последнего

уравнения, можно решить предпоследнее, т.к. после подстановки xN в нем останется неизвестным только xN-1 и т.д.
public static double [] Solve(double [,] M)
{
TriangleMatrix(M);
double v[] = new double[M.GetLength(0)];
int Nb = M.GetLength(1)-1;
for(int n = v.Length-1; n >= 0; n--)
{
double sum = 0;
for(int i = n+1; i < Nb; i++)
sum += v[i]*M[n, i];
v[n] = (M[n, Nb]-sum)/M[n, n];
}
return v;
}

Слайд 10

“Слабые” места
SubtractRow:
double m = M[k, k];
…
M[i, j] = M[i, j] -

M[k, j]*t/m;
Возможно, m окажется равным 0!
Возможно окажется неравным 0, в результате ошибок вычислений!

Слайд 11

Улучшение метода
Выбор “ведущего элемента”.
Идея заключается в том, что бы каждый раз

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

Слайд 12

Выбор ведущего элемента
//Находит строку, в которой элемент n имеет наибольшее по

модулю значение,
// и меняет ее местами со строкой n
static void SelectLeading(double [,] M, int n)
{
//Найдем номер строки, с наибольшим
//элементом в столбце n
int iMax = n;
for(int i = n+1; i < M.GetLength(0); i++)
if(Math.Abs(M[iMax, n]) < Math.Abs(M[i, n]))
iMax = i;
// Переставить строки iMax и n
if(iMax != n)
for(int i =n; i < M.GetLength(1); i++)
{
double t = M[n, i];
M[n, i] = M[iMax, i];
M[iMax, i] = t;
}
}

Слайд 13

Усовершенствованная триангуляция матрицы
static void TriangleMatrix(double [,] M)
{
for(int i = 1; i

< M.GetLength(0); i++)
{
SelectLeading(M, i-1);
SubtractRow(M, i-1);
}
}

Слайд 14

Решение есть не всегда
static bool TriangleMatrix(double [,] M)
{
for(int i = 1;

i < M.GetLength(0); i++)
{
SelectLeading(M, i-1);
if(Math.Abs(M[i-1, i-1]) > 0.0001)
SubtractRow(M, i-1);
else
retrun false;
}
return true;
}

Слайд 15

Решение
public static double [] Solve(double [,] M)
{
if(!TriangleMatrix(M))
retun null;
double v[] = new

double[M.GetLength(0)];
int Nb = M.GetLength(1)-1;
for(int n = v.Length-1; n >= 0; n--)
{
double sum = 0;
for(int i = n+1; i < Nb; i++)
sum += v[i]*M[n, i];
v[n] = (M[n, Nb]-sum)/M[n, n];
}
return v;
}

Слайд 16

Решение
double[,] M = new double[4, 5] {
{ 2, 3, 1,

1, 1 }, { 1, 2, 1, 5, 1 },
{ 1, 1, 2, 1, 1 }, { 1, 1, 4, 2, 1 } };
double[]x = Gauss.Solve(M);
if(x != null)
for (int i = 0; i < x.Length; i++)
Console.WriteLine(x[i]);
else
Console.WriteLine(“Единственного решения системы нет.”);

Слайд 17

Детерминант и метод Гаусса
Если не применять выбор ведущего элемента, то детерминант

– это просто произведение диагональных элементов верхнетреугольной матрицы.
Перестановка строк может приводить к изменению знака.
Если меняются местами строки i и j, то знак будет меняться на противоположенный.

Слайд 18

Выбор ведущего элемента
static bool SelectLeading(double [,] M, int n)
{
//Найдем номер строки,

с наибольшим
//элементом в столбце n
int iMax = n;
for(int i = n+1; i < M.GetLength(0); i++)
if(Math.Abs(M[iMax, n])
< Math.Abs(M[i, n])
iMax = i;
// Переставить строки iMax и n
if(iMax != n)
{
for(int i =n; i < M.GetLength(1); i++)
{
double t = M[n, i];
M[n, i] = M[iMax, i];
M[iMax, i] = t;
}
return true;
}
return false;
}

Слайд 19

Вычисляем детерминант
static double Determinant(double [,] M)
{
double d = 1;
for(int i =

1; i < M.GetLength(0); i++)
{
if(SelectLeading(M, i-1))
d *=-1;
if(Math.Abs(M[i-1, i-1]) > 0.0001)
SubtractRow(M, i-1);
else
retrun 0;
}
for(int i = 0; i < M.GetLength(0); i++)
d*=M[i, i];
return d;
}

Слайд 20

Контрольные вопросы
Как в решении задачи проявился характер вычислений с числами с

плавающей точкой?
Какие преобразования числовых типов компилятор выполняет сам?
Как преобразовать числовые типы, если компилятор не позволяет неявное преобразование?

Слайд 21

Вычисление числа Пи методом “Монте-Карло”
Метод основан на применении для вычислений случайных

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

Слайд 22

Вычисление числа Пи
Sокр = Пи*R2
Удобно взять R = 1 и ограничиться

1-ой четвертью математической плоскости.
Sокр = Пи
Площадь квадрата при этом равна 4.

Слайд 23

Вычисление Пи Реализация
int N=1000000;
int n=0;
Double x, y;
Random r = new Random();
for(int i

= 0; i < N; i++)
{
x = r.NextDouble(); y = r.NextDouble();
if(x*x + y*y < 1)
n++;
}
Double pi = (4.0 * n) / N;
Console.WriteLine(“Pi = {0:0.###}”, pi);

ПЯВУ. Основы программирования. Лекция 14. Решение системы уравнений методом Гаусса. Вычисление числа Пи методом “МонтеКарло”

Содержание

Контрольные вопросыПочему в C# рекомендуют использовать свойства вместо полей данных?Что такое

План лекцииРешение системы уравнений методом ГауссаВариант с выбором ведущего элементаВычисление детерминанта

Системы линейных уравнений и Матрицы a11*x1 + a12*x2 + … a1N*xN =

Метод Гаусса a’11*x1 + a’12*x2 + … a’1N*xN = b’1 a’22*x2 +

Представление системы уравненийМатрицу представим в виде двумерного массива:double [,] M =

Алгоритм вычитания строкЗдесь k – номер строки, которую надо вычитать …static

Приведение матрицы к верхнетреугольному видуstatic void TriangleMatrix(double [,] M){ for(int i =

РешениеПоследнее уравнение содержит только 1 неизвестное – xN. После решения последнего

“Слабые” местаSubtractRow: double m = M[k, k]; … M[i, j] = M[i, j] -

Улучшение методаВыбор “ведущего элемента”.Идея заключается в том, что бы каждый раз

Выбор ведущего элемента//Находит строку, в которой элемент n имеет наибольшее по

Усовершенствованная триангуляция матрицыstatic void TriangleMatrix(double [,] M){ for(int i = 1; i

Решение есть не всегдаstatic bool TriangleMatrix(double [,] M){ for(int i = 1;

Решениеpublic static double [] Solve(double [,] M){ if(!TriangleMatrix(M)) retun null; double v[] = new

Решениеdouble[,] M = new double[4, 5] { { 2, 3, 1,

Детерминант и метод ГауссаЕсли не применять выбор ведущего элемента, то детерминант

Выбор ведущего элементаstatic bool SelectLeading(double [,] M, int n){ //Найдем номер строки,

Вычисляем детерминантstatic double Determinant(double [,] M){ double d = 1; for(int i =

Контрольные вопросыКак в решении задачи проявился характер вычислений с числами с

Вычисление числа Пи методом “Монте-Карло”Метод основан на применении для вычислений случайных

Вычисление числа ПиSокр = Пи*R2Удобно взять R = 1 и ограничиться

Вычисление Пи Реализацияint N=1000000;int n=0;Double x, y;Random r = new Random();for(int i

Похожие презентации