Учебное пособие_Численные методы -26 -дек_2014 (97-2003)
.pdf
переменных x1, x2, x3, которые являются решением системы с заданной точностью. Приближенные значения уровней выпуска для трех отраслей равны: x1 662,3, x2 1188,1, x3 1301,3. Если корни все еще не появились, необходимо продолжить копирование до тех пор, пока в строке 12 не появится сообщение «да», значит искомые корни найдены.
10. Построить диаграмму, показывающую процесс приближения значения переменных x1, x2, x3 к решению системы. Диаграмма строится в режиме «Точечная», где по оси абсцисс откладывается номер итерации.
Пример 2.5
Предприятие выпускает три вида продукции, используя сырье трех видов. Необходимые характеристики производства указаны в таблице 1. Требуется определить объем выпуска продукции каждого вида при заданных запасах сырья.
|
|
|
|
|
Таблица 2. 1 |
|
|
|
Исходные данные |
|
|
||
|
|
|
|
|
|
|
Вид сырья |
Расход сырья по видам |
Запас сырья, вес. ед. |
|
|||
|
продукции, вес. ед. изд. |
|
|
|||
|
1 |
|
2 |
3 |
|
|
1 |
6 |
|
4 |
1 |
2400 |
|
2 |
1 |
|
3 |
1 |
1450 |
|
3 |
2 |
|
2 |
5 |
1550 |
|
x1
,
x
Решение. Обозначим неизвестные объемы выпуска продукции через 2 , x3 . Тогда при условии полного расхода запасов каждого вида сырья
можно записать балансовые соотношения, которые образуют систему трех уравнений с тремя неизвестными:
6x1 4x2 x3 2400,x1 3x2 x3 1450,2x1 2x2 5x3 1550.
Расширенная матрица системы:
|
6 |
4 |
1 |
2400 |
|
|
|
|
|
|
1 |
3 |
1 |
1450 . |
|
|
|
|
|
|
2 |
2 |
5 |
1550 |
Метод Гаусса. Ручной счет
Прямой ход:
61
|
6 |
4 |
1 |
|
|
|
|
|
1 |
3 |
1 |
|
2 |
2 |
5 |
|
2400 1450
1550
6 →2
1 |
0,667 |
0,167 |
|
|
|
1 |
3 |
1 |
|
|
|
1 |
1 |
2,5 |
400 |
|
|
|
|
|
1строка |
|
|
|
||
1450 |
|||
775 |
|
1строка |
|
|
|||
|
|
||
→
|
|
1 |
0,667 |
0,167 |
→ |
|
|
|
|
|
0 |
2,333 |
0,833 |
|
|
|
0 |
0,333 |
2,333 |
|
|
400 |
|
|
|
|
|
|
|
|
|
||
1050 |
|||
375 |
|
|
|
|
|||
|
|
||
2,333 0,333
→
|
1 |
0,667 |
0,167 |
|
|
|
|
|
0 |
1 |
0,357 |
|
0 |
1 |
7,006 |
|
400 |
|
|
|
|
|
|
|
450,064 |
|
|
|
1126,126 |
|
2 строка |
|
|
|||
|
|
→
|
|
1 |
0,667 |
0,167 |
→ |
|
|
|
|
|
0 |
1 |
0,357 |
|
|
|
0 |
0 |
6,649 |
|
|
Обратный ход:
x3 101,679 ,
400 |
|
|
|
|
|
|
|
450,064 |
|
||
676,062 |
|
|
|
|
|||
|
|
||
6,649
|
1 |
|
|
→ |
0 |
|
0 |
|
0,667 |
0,167 |
1 |
0,357 |
0 |
1 |
400 |
|
|
|
450,064 |
|
101,679 |
|
|
|
.
x |
2 |
|
450,064 0,357 x |
3 |
|
450,064 0,357 101,679
413,765
,
x |
400 0,167x |
3 |
0,667x |
2 |
400 0,167 101,679 0,667 413,765 107,038 . |
1 |
|
|
|
Ответ:
x1
107,038
,
x |
2 |
|
413,765
,
x |
3 |
|
101,679
.
Метод Гаусса. Решение в Microsoft Excel показано на рис. 2.11.
62
Рис. 2.11. Метод Гаусса (решение в Microsoft Excel)
Метод простой итерации. Решение в Microsoft Excel представлен на рис. 2.12. В расчетах использована точность 0,1.
Рис. 2.12. Метод простой итерации (решение в Microsoft Excel)
Комментарий. При заданной точности 0,1 решение системы уравнений получено за 31 итерацию. Если задать более высокую точность
63
0,01, то решение будет получено за 39 итераций. При точности 0,001 решение получается за 48 итераций.
Метод Зейделя. Решение в Microsoft Excel представлен на рис. 2.13.
Рис. 2.13. Метод Зейделя (решение в Microsoft Excel)
Комментарий. При заданной точности 0,1 решение системы уравнений получено за 8 итераций. Если задать более высокую точность 0,01, то решение будет получено за 11 итераций. При точности 0,001 решение получается за 12 итераций.
Метод простой итерации, метод Зейделя. Решение в Microsoft Visual Studio
Код программы на языке С++:
// pr1 SLAU ekonom.cpp: определяет точку входа для консольного приложения.
#include"stdafx.h" #include<iostream> #include<math.h> usingnamespace std;
double a[3][3]={{6, 4, 1}, {1, 3, 1}, {2, 2, 5}};
double b[3]={2400, 1450, 1550}; double x[3]={0, 0, 0};
double e=0.1;
bool shod(double a[3][3]){
bool s0=fabs(a[0][0])>fabs(a[0][1])+fabs(a[0][2]); bool s1=fabs(a[1][1])>fabs(a[1][0])+fabs(a[1][2]); bool s2=fabs(a[2][2])>fabs(a[2][0])+fabs(a[2][1]); if(s0 && s1 && s2)returntrue;
elsereturnfalse;
}
bool toch(double b[3], double c[3]){ int i=0;
for(i=0; i<3; i++){ if(fabs(b[i]-c[i])>e){ returnfalse;
}
}
returntrue;
}
64
void pr_iter(){
double x0[3]={-1,-1,-1}; int k_iter=0, i; if(shod(a)==true){ while(toch(x0,x)==false){ k_iter++;
for(i=0; i<3; i++){ x0[i]=x[i];
}
x[0]=(b[0]-a[0][1]*x0[1]-a[0][2]*x0[2])/a[0][0]; x[1]=(b[1]-a[1][0]*x0[0]-a[1][2]*x0[2])/a[1][1]; x[2]=(b[2]-a[2][0]*x0[0]-a[2][1]*x0[1])/a[2][2];
}
}
cout<<"Metod prostoi iteracii: k = "<<k_iter<<endl; for(i=0; i<3; i++){
cout<<"\tx["<<i+1<<"] = "<<x[i]<<endl;
}
}
void zeid(){
double x0[3]={-1,-1,-1}; int k_iter=0, i;
for(i=0; i<3; i++) x[i]=0; if(shod(a)==true){ while(toch(x0,x)==false){ k_iter++;
for(i=0; i<3; i++){ x0[i]=x[i];
}
x[0]=(b[0]-a[0][1]*x0[1]-a[0][2]*x0[2])/a[0][0]; x[1]=(b[1]-a[1][0]*x[0]-a[1][2]*x0[2])/a[1][1]; x[2]=(b[2]-a[2][0]*x[0]-a[2][1]*x[1])/a[2][2];
}
}
cout<<"Metod Zeidelya: k = "<<k_iter<<endl; for(i=0; i<3; i++){
cout<<"\tx["<<i+1<<"] = "<<x[i]<<endl;
}
}
int main(){ cout<<"e="<<e<<endl; pr_iter();
zeid(); return 0;
}
Результаты выполнения программы с различной точностью представлены на рис. 2.14 – рис. 2.16.
Рис. 2.14. Результат выполнения программы с точностью 0,1
65
Рис. 2.15. Результат выполнения программы с точностью 0,01
Рис. 2.16. Результат выполнения программы с точностью 0,001
Решая эту систему уравнений любым из приведенных способов, находим, что при заданных запасах сырья объемы выпуска продукции
составляет |
по |
каждому |
виду соответственно (в условных |
единицах): x1 |
107 , |
x2 414, x3 |
101. |
Пример 2.6
На предприятие с работниками четырех категорий привезли заработную плату в купюрах следующего достоинства: по 100 рублей – 1 850 купюр, по 50 рублей – 230 купюр, по 10 рублей – 250 купюр, по 1 рублю – 740 купюр. Заработная плата работника 1-й категории составляет 962 руб., 2- й категории – 713 руб., 3-й категории – 452 руб., 4-й категории – 261 руб. Определить, сколько сотрудников каждой категории работает на предприятии, если каждому выдали заработную плату минимальным числом купюр.
Решение. Условие об оплате минимальным числом купюр является основным в определении количества купюр разного достоинства, выданных сотрудникам разных категорий. Исходя из величины заработной платы по категориям, однозначно определяем таблицу распределения купюр.
Таблица 2.2
Исходные данные
66
Достоинство |
|
Распределение купюр по |
|
Общее количество |
|||
купюры, руб. |
|
|
категориям |
|
купюр |
||
|
1 |
|
2 |
3 |
|
4 |
|
100 |
9 |
|
7 |
4 |
|
2 |
1850 |
50 |
1 |
|
- |
1 |
|
1 |
230 |
10 |
1 |
|
1 |
- |
|
1 |
250 |
1 |
2 |
|
3 |
2 |
|
1 |
740 |
Пусть x1 , x2 , x3 , x4 количество работников категорий
соответственно с первой по четвертую. Тогда по данным табл. 2.2 составляем уравнения «баланса», которые образуют систему из четырех уравнений с четырьмя неизвестными:
9x1 7x2 4x3 2x4 185,
x1 x3 x4 230,x1 x2 x4 250,
2x1 3x2 2x3 x4 740.
Эту систему удобно решать методом Гаусса, для чего выпишем расширенную матрицу системы, предварительно переместив для удобства первое уравнение на последнее место. Прямой ход метода последовательно меняет вид матрицы:
1 |
|
0 |
1 |
1 |
230 |
|
|
1 |
0 |
|
1 |
1 |
|
230 |
|
|
|
1 |
0 |
1 |
1 |
230 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
||
1 |
|
1 |
0 |
1 |
250 |
|
|
|
0 |
1 |
0 |
20 |
|
|
|
0 |
1 |
0 |
20 |
|
|
||||||||
|
2 |
|
3 |
2 |
1 |
740 |
|
|
0 |
3 |
0 |
1 |
280 |
|
|
|
0 |
0 |
3 |
1 |
220 |
|
|||||||
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
9 |
|
7 |
4 |
|
|
|
|
|
0 |
7 |
5 |
7 220 |
|
|
|
0 |
0 |
2 |
7 360 |
|
|
|||||||
|
|
2 1850 |
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
1 |
0 |
1 |
1 |
230 |
|
|
1 |
0 |
1 |
1 |
|
230 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
20 |
|
|
|
0 |
1 |
0 |
|
20 |
|
|
. |
|
|
|
|
|
|
|||||||
|
0 |
0 |
2 |
7 |
360 |
|
|
0 |
0 |
2 |
7 |
360 |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
0 |
0 |
3 |
1 |
220 |
|
|
|
0 |
0 |
0 |
19 2 |
|
760 |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Полученная в цепочке прямого хода расширенная матрица соответствует системе уравнений, эквивалентной исходной системе:
x |
x |
3 |
|
x |
4 |
230, |
|||||
|
1 |
|
|
|
|
|
|
|
|||
|
x3 |
20, |
|||||||||
x2 |
|||||||||||
|
2x |
|
7x |
|
360, |
||||||
|
3 |
4 |
|||||||||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
760. |
|||||
19 2 x |
4 |
||||||||||
|
|
|
|
|
|
|
|
|
|
||
Обратным
x4 80, x3
ходом метода
100, x2 120 , x1
получаем последовательно неизвестные:
50.
67
Контрольные вопросы
1.На какие два метода делятся численные методы решения систем линейных уравнений?
2.Какой метод предпочтительнее использовать для решения системы из 500 линейных уравнений?
3.Из каких двух стадий состоит метод Гаусса, и в чем они заключаются?
4.Какой из методов сходится быстрее – метод простой итерации или метод Зейделя?
5.В чем отличие метода простой итерации от метода Зейделя?
6.В чем заключается метод LU разложения?
7.Что такое матрица отражений? Докажите, что она является самосопряженной и унитарной.
8.В чем заключается геометрический смысл преобразования, задаваемого матрицей отражения?
9.В чем заключается суть метода отражений?
10.Какие методы являются универсальными, а какие требуют выполнения некоторых условий?
68
3. Решение нелинейных уравнений
Для решения нелинейного уравнения существует множество методов.
|
Среди них метод дихотомии |
|
|
|
|
|
||||||||
|
(от греческого «дихо» - на |
|
|
|
|
|
||||||||
|
две части, «томи» -сечение), |
|
|
|
|
|
||||||||
|
он |
же |
метод |
половинного |
|
|
|
|
|
|||||
|
деления; |
метод |
Ньютона |
|
|
|
|
|
||||||
|
(метод |
|
касательных), |
|
|
|
|
|
||||||
|
который |
был |
разработан |
|
|
|
|
|
||||||
|
Исааком |
Ньютоном |
в |
|
|
|
|
|
||||||
|
1669 г., получив улучшение |
|
|
|
|
|
||||||||
|
в |
1948 |
г. |
в |
работах |
Л.В. Канторович |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
||||
И. Ньютон |
Л.В. |
Канторовича; |
метод |
|
(1912 – 1986) |
|
|
|||||||
(1642 – 1727) |
простой итерации |
и |
метод |
|
|
|
|
|
||||||
|
золотого сечения, дошедший до нас из античной |
|||||||||||||
литературы. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Метод золотого сечения впервые встречается во 2-й книге «Начал» |
||||||||||||||
Евклида, где даётся его |
геометрическое построение, равносильное |
|||||||||||||
|
решению квадратного уравнения вида |
x a x a |
2 |
. |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Евклид применяет золотое сечение при |
|||||||||||||
|
построении правильных 5- и 10-угольников (6 и 14 |
|||||||||||||
|
книги), а также в стереометрии при построении |
|||||||||||||
|
правильных 12- и 20-гранников. Несомненно, что |
|||||||||||||
|
золотое сечение было известно и до Евклида. |
|||||||||||||
|
Весьма вероятно, что этим методом были решены |
|||||||||||||
|
задачи |
|
ещё |
пифагорейцами, |
которым |
|||||||||
|
приписываются построение правильного 5- |
|||||||||||||
Эвклид |
угольника |
и |
|
геометрические |
построения, |
|||||||||
равносильные |
решению |
квадратного |
уравнения. |
|||||||||||
(ок. 325 года до н. э) |
||||||||||||||
После |
Евклида |
исследованием |
|
этого метода |
||||||||||
|
|
|||||||||||||
занимались Гипсикл (II в. до н. э.), Папп Александрийский (III в. н. э.) и др.
В средневековой Европе с методом познакомились по арабским переводам «Начал» Евклида. Переводчик и комментатор Евклида Дж. Кампано из Новары (XIII в.) добавил к 13 книге «Начал» предложение, содержащее арифметическое доказательство несоизмеримости отрезка и обеих частей его золотым сечением. В XV-XIV вв. усилился интерес к
69
методу среди учёных и художников в связи с его применением в
искусстве, особенно в архитектуре. |
|
|
||
|
Л. |
Пачоли |
посвятил |
|
|
золотому сечению трактат «О |
|
||
|
божественной |
пропорции», |
|
|
|
вышедшей в 1509 г. Много |
|
||
|
писал о методе в одном из своих |
|
||
|
ранних произведений И. Кеплер |
|
||
|
(1596 г.). |
|
|
|
|
Термин «3олотое сечение» |
|
||
Л. Пачоли |
ввёл Леонардо да Винчи (кон. |
|
||
XV в.). |
Золотое |
сечение или |
|
|
(1445 – 1517) |
Ф.Брунеллески |
|||
|
близкие ему пропорциональные |
|||
|
(1377-1446) |
|||
отношения легли |
в основу композиционного |
|
||
построения многих произведений мирового искусства, например, архитектуры античности и Возрождения: Капелла Пацци во Флоренции (архитектор Ф. Брунеллески, XV в.).
3.1. Отделение корней
Если алгебраическое или трансцендентное уравнение достаточно сложно, то его корни сравнительно редко удается найти точно. Кроме того, в некоторых случаях уравнение содержит коэффициенты, известные лишь приблизительно, и, следовательно, сама задача о точном определении корней уравнения теряет смысл. Поэтому важное значение приобретают способы приближенного нахождения корней уравнения и оценки степени их точности [11].
Пусть дано уравнение
f (x) 0 |
, |
(3.1) |
где функция f (x) определена и непрерывна в некотором конечном или бесконечном интервале a<x<b. Всякое значение x0, обращающее функцию f (x) в нуль, т. е. такое, что f (x0 ) 0 , называется корнем уравнения (3.1) или нулем функции f (x) . Мы будем предполагать, что уравнение (3.1) имеет лишь изолированные корни, т. е. для каждого корня уравнения (3.1) существует окрестность, не содержащая других корней этого уравнения.
Приближенное нахождение изолированных действительных корней уравнения (3.1) обычно складывается из двух этапов:
1) отделение корней, то есть установление возможно тесных промежутков [a, b], в которых содержится один и только один корень уравнения (3.1);
70