Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕНЫЙ УНИВЕРСИТЕТ»
Факультет информационных технологий
Кафедра информационных систем и технологий
Отчет по лабораторной работе №2 «Численные методы и теория оптимизации»
ОГУ 230201.9009.12 ОО
Руководитель работы
____________ Пивоваров Ю.Н.
«__»_________________2013 г.
Исполнитель
Студент группы 12 ИСТ(б)ОП
_____________ Лемясов
«__»_________________2013 г.
Оренбург 2013
Содержание
1. Задание………………………………………………….………………………….3
2. Теоретические сведения…………………………….…………………………….4
3. Ход работы…………………………………………………………………….....14
4. Список использованной литературы…………….……………………………..16
5. Приложения………………………………….…………………………………...17
Задание
Даны три системы уравнения:
Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса.
Вычисления с помощью метода Гаусса заключаются в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с верхней треугольной матрицей. Вычисления значений неизвестных производят на этапе обратного хода.
Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления
Прямой ход состоит из n 1 шагов исключения.
1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a11 0. Будем называть его главным элементом 1-го шага.
Найдем величины
qi1 = ai1/a11 (i = 2, 3, …, n),
называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31, …, qn1. Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему
a11x1 + a12x2 + a13x3 + … + a1nxn = b1 ,
a22(1)x2 + a23(1)x3 + … + a2n(1)xn = b2(1) ,
a32(1)x2 + a33(1)x3 + … + a3n(1)xn = b3(1) ,
an2(1)x2 + an3(1)x3 + … + ann(1)xn = bn(1) .
в которой aij(1) и bij(1) вычисляются по формулам
aij(1) = aij − qi1a1j , bi(1) = bi − qi1b1.
2-й шаг. Целью этого шага является исключение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22(1) ≠ 0, где a22(1) – коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага
qi2 = ai2(1) / a22(1) (i = 3, 4, …, n)
и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2. В результате получим систему
a11x1 + a12x2 + a13x3 +… + a1nxn = b1,
a22(1)x2 + a23(1)x3 +… + a2n(1) = b2(1),
a33(2)x3 +… + a3n(2)xn = b3(2),
an3(2)x3 +… + ann(2)xn = bn(2).
Здесь коэффициенты aij(2) и bij(2) вычисляются по формулам
aij(2) = aij(1) – qi2a2j(1) , bi(2) = bi(1) – qi2b2(1).
Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.
k-й шаг. В предположении, что главный (ведущий) элемент k-го шага akk(k–1) отличен от нуля, вычислим множители k-го шага
qik = aik(k–1) / akk(k–1) (i = k + 1, …, n)
и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на qk+1,k, qk+2,k, …, qnk.
После (n - 1)-го шага исключения получим систему уравнений
a11x1 + a12x2 +a13x3 +… + a1nxn =b1,
a22(1)x2 +a23(1)x3 +… +a2n(1)xn = b2(1),
a33(2)x3 +… +a3n(2)xn =b3(2) ,
ann(n–1)xn =bn(n–1)
матрица A(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.
Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное
значение xn в предпоследнее уравнение, получим xn–1. Осуществляя обратную подстановку, далее последовательно находим xn–1, xn–2, …, x1. Вычисления неизвестных здесь проводятся по формулам
xn = bn(n–1) / ann(n–1),
xk = (bn(k–1) – ak,k+1(k–1)xk+1 – … – akn(k–1)xn) / akk(k–1), (k = n – 1, …, 1).
Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akk(k–1). Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.
1.1.2 Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам
aij(k) = aij(k–1) − qikakj , bi(k) = bi(k–1) − qikbk(k–1) , i = k + 1, …, n.
Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей qik.
В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |qik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной xk в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента akk(k-1). После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.
Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных.
На 1-м шаге мтода среди элементов aij определяют максимальный по модулю элемент ai1j1. Первое уравнение системы и уравнение с номером i1 меняют местами. Далее стандартным образом производят исключение неизвестного xi1 из всех уравнений, кроме первого.
На k-м шаге метода среди коэффициентов aij(k–1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент aikjk(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i = k + 1, …, n.
На этапе обратного хода неизвестные вычисляют в следующем порядке: xjn, xjn–1, …, xj1.
Метод итераций
Запишем систему нелинейных уравнений в виде
(1.1)
или коротко в виде, где .
Здесь функции, стоящие слева в (1.1) определены и непрерывны вместе со своими частными производными в некоторой области D, которой принадлежит точное решение рассматриваемой системы уравнений. Точное решение системы (1.1) обозначим
(1.2)
Для того, чтобы систему (1.1) решить методом простой итерации, во-первых, преобразуем её к виду
(1.3)
или, коротко к виду, , где .
Функции, стоящие справа в (1.3) обладают теми же свойствами, что и функции в (1.1).
Во-вторых, в области D выберем любую точку и назовём её нулевым приближением к точному решению системы (1.3).
В-третьих, координаты точки подставим в правую часть системы (1.3) и вычислим значения величин, стоящих слева в этой системе.
Будем иметь
(1.4)
или коротко
Величины , стоящие слева в формулах (1.4), будем считать координатами точки . Эту точку назовём первым приближением к точному решению исходной системы, т.е. к . Теперь мы имеем два приближённых решения системы (1.3). Этими решениями являютсяи .
В четвёртых, сравним эти два приближённых решения на:
(1.5)
или коротко
Если все неравенства (1.5) выполняются, то за приближённое решение исходной системы можно выбрать как , так и , поскольку эти два решения отличаются друг от друга не больше чем на .
На этом решение исходной системы методом простой итерации заканчивается. Если же хотя бы одно из неравенств (1.5) не выполняется, то надо компоненты первого приближения подставить в правую часть системы (1.3) и вычислить второе приближение . Здесь
(1.6)
или коротко
Далее надо сравнить приближения и на по формуле (1.5). Строить приближения надо до тех пор, пока два соседних приближения и будут отличаться друг от друга не больше чем на .
Запишем рабочие формулы метода простой итерации для системы (1.3) в компактном виде.
Вычислить
(1.7)
и построить приближения к решению системы (1.3)
для всех и (1.8)
Сформулируем алгоритм вычислений по формулам (1.7) и (1.8).
Выберем , принадлежащую D.
В (1.7) положим , получим
По (1.8) построим .
Проверим условие (1.5) на :
Если все условия в п.4 выполнены, то заканчиваем вычисления, выбрав за приближённое решение исходной системы или всё равно, т.к. эти решения отличаются друг от друга не больше чем на . Если хотя бы одно из условий в п.4 не выполнилось, то переходим к п.6.
В (1.7) положим и получим
По (1.8) построим .
Перейдём к п.4, при этом верхние индексы в условии (1.5) изменятся и станут на единицу больше.
Метод Зейделя
Приведение системы к виду, удобному для итераций. Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений
Ax = b
с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду
x = Bx + c.
Здесь B – квадратная матрица с элементами bij (i, j = 1, 2, …, n), c – вектор-столбец с элементами cij (i = 1, 2, …, n).
В развернутой форме записи система имеет следующий вид:
x1 = b11x1 + b12x2 + b13x3 + … + b1nxn + c1
x2 = b21x1 + b22x2 + b23x3 + … + b2nxn + c2
xn = bn1x1 + bn2x2 + bn3x3 + … + bnnxn + cn
Вообще говоря, операция приведения системы к виду, удобному для итераций, не является простой и требует специальных знаний, а также существенного использования специфики системы.
Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x1:
x1 = a11–1 (b1 – a12x2 – a13x3 – … – a1nxn),
из второго уравнения – неизвестное x2:
x2 = a21–1 (b2 – a22x2 – a23x3 – … – a2nxn),
и т. д. В результате получим систему
x1 = b12x2 + b13x3 +… +b1,n–1xn–1 +b1nxn+c1 ,
x2 = b21x1 + b23x3 +… +b2,n–1xn–1 + b2nxn+c2 ,
x3 = b31x1 + b32x2 +… +b3,n–1xn–1 + b3nxn+c3 ,
xn = bn1x1 + bn2x2 +bn3x3 +… +bn,n–1xn–1 +cn ,
В которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам
bij = –aij / aii, ci = bi / aii (i, j = 1, 2, …, n, j ≠ i)
Конечно, для возможности выполнения указанного преобразования необходимо, чтобы диагональные элементы матрицы A были ненулевыми.
Заметим, что B = B1 + B2 и поэтому решение x исходной системы удовлетворяет равенству
x = B1x + B2 x + c .
Выберем начальное приближение x(0) = [x1(0), x2(0), …, xn(0)]T. Подставляя его в правую часть равенства при верхней треугольной матрице B2 и вычисляя полученное выражение, находим первое приближение
x(1) = B1x(0) + B2x(1)
Подставляя приближение x(1), получим
x(2) = B1x(1) + B2x(2)
Продолжая этот процесс далее, получим последовательность x(0), x(1), …, x(n), … приближений к вычисляемых по формуле
x(k+1) = B1(k+1) + B2(k) + c
или в развернутой форме записи
x1(k+1) =b12x2(k) + b13x2(k) +… +b1nxn(k) +c1 ,
x2(k+1) =b21x1(k+1) + b23x3(k) + … +b2nxn(k) +c2 ,
x3(k+1) =b31x1(k+1) + b32x2(k+1) + … +b3nxn(k) +c3 ,
xn(k+1) =bn1x1(k+1) + bn2x2(k+1) + bn3x3(k+1) + … + cn .
Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим
xi(k+1) = xi(k) – aii–1(∑j=1i–1 aijxj(k+1) + ∑j=1n aijxi(k) – bi).
Тогда достаточным условием сходимости метода Зейделя будет
∑j=1, j≠i n | a ij | < | a ii | (условие доминирования диагонали).
Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.
Сравнение прямых и итерационных методов
Системы линейных алгебраических уравнений можно решать как с помощью прямых, так и итерационных методов. Для систем уравнений средней размерности чаще используют прямые методы.
Итерационные методы применяют главным образом для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций. Большие системы уравнений, возникающие в основном в приложениях, как правило, являются разреженными. Методы исключения для систем с разреженным и матрицами неудобны, например, тем, что при их использовании большое число нулевых элементов превращается в ненулевые и матрица теряет свойство разреженности. В противоположность им при использовании итерационных методов в ходе итерационного процесса матрица не меняется, и она, естественно, остается разреженной. Большая эффективность итерационных методов по сравнению с прямыми методами тесно связанна с возможностью существенного использования разреженности матриц.
Применение итерационных методов для качественного решения большой системы уравнений требует серьезного использования ее структуры, специальных знаний и определенного опыта.
Ход работы
Метод Гаусса
Решим систему уравнения:
Получим ответы:
Метод итераций
Решим систему уравнения:
Получим ответы:
Метод Зейделя
Решим систему уравнения:
Получим ответы:
Список использованной литературы
математике».
Приложение А
Схемы алгоритмов
Алгоритмы решения задач
Рисунок А.1 - Алгоритм по методу Гауса
Рисунок А.2 - Алгоритм по методу итераций
Рисунок А.3 - Алгоритм по методу Зейделя
Приложение Б
Листинги программ
Метод Гауса
#include <conio.h>
#include <math.h>
#include <stdio.h>
main()
{
FILE *fp;
int i,j,k;
double a[10][10][10],b[10][10][10],x[10];
fp=fopen("fgaus.txt","r");
k=0;
for(i=1;i<=4;i++)
{
for(j=1;j<=5;j++)
{
fscanf(fp,"%lf",&a[i][j][k]);
}
}
fclose(fp);
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
printf("%6g ",a[i][j][k]);
}
printf(" = %6g\n",a[i][j][k]);
}
printf("\n");
for(j=2;j<=5;j++)
{
b[1][j][k]=a[1][j][k]/a[1][1][k];
}
for(k=1;k<=3;k++)
{
for(i=k+1;i<=4;i++)
{
for(j=k+1;j<=5;j++)
{
a[i][j][k]=a[i][j][k-1]-a[i][k][k-1]*b[k][j][k-1];
}
}
for(j=k+2;j<=5;j++)
{
b[k+1][j][k]=a[k+1][j][k]/a[k+1][k+1][k];
}
}
for(i=4;i>=1;i--)
{
x[i]=b[i][5][i-1];
for(j=4;j>=i;j--)
{
x[i]-=b[i][j][i-1]*x[j];
}
}
for(i=1;i<=4;i++)
{
printf("x%d=%g ",i,x[i]);
}
getch();
return(0);
}
Метод итераций
#include <conio.h>
#include <math.h>
#include <stdio.h>
main()
{
FILE *fp;
int i,j,k;
double a[10][10],b[10],x[10][50],eps=0.001;
fp=fopen("fiterslau.txt","r");
for(i=1;i<=3;i++)
{
for(j=1;j<=3;j++)
{
fscanf(fp,"%lf",&a[i][j]);
}
fscanf(fp,"%lf",&b[i]);
}
fclose(fp);
for(i=1;i<=3;i++)
{
b[i]/=a[i][i];
for(j=1;j<=3;j++)
{
if(i!=j)
{
a[i][j]=-a[i][j]/a[i][i];
}
}
a[i][i]=0;
}
printf("k x1 x2 x3\n");
printf("0 ");
for(i=1;i<=3;i++)
{
x[i][0]=b[i];
printf("%-10g ",x[i][0]);
}
k=1;
n1:
printf("\n%-2d ",k);
for(i=1;i<=3;i++)
{
x[i][k]=b[i];
for(j=1;j<=3;j++)
{
if(i!=j)
{
x[i][k]+=a[i][j]*x[j][k-1];
}
}
printf("%-10g ",x[i][k]);
}
for(i=1;i<=3;i++)
{
if(fabs(x[i][k]-x[i][k-1])<eps)
{
goto n2;
}
}
k++;
goto n1;
n2:
getch();
return(0);
}
Метод Зейделя
#include <conio.h>
#include <math.h>
#include <stdio.h>
main()
{
FILE *fp;
int i,j,k;
double a[10][10],b[10],x[10][50];
fp=fopen("fzeid.txt","r");
for(i=1;i<=3;i++)
{
for(j=1;j<=3;j++)
{
fscanf(fp,"%lf",&a[i][j]);
}
fscanf(fp,"%lf",&b[i]);
}
fclose(fp);
for(i=1;i<=3;i++)
{
b[i]/=a[i][i];
for(j=1;j<=3;j++)
{
if(i!=j)
{
a[i][j]=-a[i][j]/a[i][i];
}
}
a[i][i]=0;
}
printf("k x1 x2 x3\n");
printf("0 ");
for(i=1;i<=3;i++)
{
x[i][0]=b[i];
printf("%-10g ",x[i][0]);
}
k=1;
n1:
printf("\n%-2d ",k);
for(i=1;i<=3;i++)
{
x[i][k]=b[i];
for(j=i+1;j<=3;j++)
{
if(i!=j)
{
x[i][k]+=a[i][j]*x[j][k-1];
}
}
for(j=1;j<i;j++)
{
if(i!=j)
{
x[i][k]+=a[i][j]*x[j][k];
}
}
printf("%-10g ",x[i][k]);
}
k++;
if(k<=5)
{
goto n1;
}
getch();
return(0);
}
2
Лист
3
Лист
x[i]=b[i][5][i-1]
i=4; i>=1; i--
Вывод x[i]
24
Лист
23
Лист
22
Лист
21
Лист
20
Лист
19
Лист
18
Лист
+
+
b[k+1][j][k]=a[k+1][j][k]/
/a[k+1][k+1][k]
j=k+2; j<=5; j++
a[i][j][k]=a[i][j][k-1]-a[i][k][k-1]* *b[k][j][k-1]
k=1; k<=3; k++
=k+1; i<=4; i++
j=k+1; j<=5; j++
b[1][j][k]=a[1][j][k]/a[1][1][k]
j=2; j<=5; j++
Ввод a[i][j][k]
k=0
End
Start
17
Лист
16
Лист
15
Лист
14
Лист
13
Лист
10
Лист
12
Лист
11
Лист
9
Лист
8
Лист
7
Лист
6
Лист
5
Лист
4
Лист
x[i]-=b[i][j][i-1]*x[j]
j=4; j>=i; j--
нет
начало
X0=( )
к=0
да
вывод
или
конец
к=к+1