Методы, используемые для отделения корней уравнения с одной переменной

Содержание

1.	Этапы решения прикладных задач. Машинное представление числа. Числа с плавающей точкой......................
Приближенные...................................................................................................................................................................
2.	Неустойчивость алгоритмов..........................................................................................................................................
3.	Структура полной погрешности эксперимента............................................................................................................
4.	Методы, используемые для отделения корней уравнения с одной переменной...................................................
5.	Уточнение корней методом половинного деления. Алгоритм, блок-схема.............................................................

 

6. Уточнение корней методом простой итерации. Теорема, алгоритм геометрическая иллюстрация. Оценка

 

погрешности метода........................................................................................................................................................................................... 8

 

7. Метод касательных(Ньютона). Сходимость метода, оценка погрешности, геометрическая интерпретация. 10

 

8. Метод хорд. Сходимость метода, оценка погрешности, геометрическая интерпретация...................................... 11

 

9. Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод

 

Гаусса, алгоритм, блок схема........................................................................................................................................................................ 12

 

Метод Гаусса.................................................................................................................................................................................................... 13

 

10. Решение систем линейных алгебраических уравнений. Требования к сходимости итерационного процесса.

 

............................................................................................................................................................................................ 15

 

11. Оценка погрешности метода простой итерации......................................................................................................................... 16

 

12. Метод Зейделя............................................................................................................................................................................................. 17

 

13. Постановка задачи интерполирования. Параболическая интерполяция. единственность задачи

 

интерполирования многочленами............................................................................................................................................................ 20

 

14. Интерполяционный многочлен Лагранжа...................................................................................................................................... 21

 

15. многочлен Ньютона для равноотстоящих узлов.......................................................................................................................... 23

 

16. Численное интегрирование. Квадратурные формулы Ньютона-Котеса......................................................................... 26

 

17.Формула трапеций. Геометрическая иллюстрация. Оценка погрешности..................................................................... 28

 

18. Формула Симпсона. Алгоритм, блок-схема. Геометрическая иллюстрация. Оценка погрешности................. 29

 

19. Решение обыкновенных дифференциальных уравнений. Численное интегрирование уравнений порядка

 

выше, чем первый. Решение систем дифференциальных уравнений.................................................................................... 31

 

20. Метод Эйлера численного интегрирования дифференциального уравнения. Алгоритм, блок-схема.

 

Недостатки метода............................................................................................................................................................................................ 33

 

21. Методы Рунге-Кутта. Расчетные формулы, алгоритм, блок-схема, погрешность метода..................................... 35

 

22. Методы обработки данных. Метод наименьших квадратов. Общий случай................................................................ 36

 

23.Линейная и квадратичная регрессия.................................................................................................................................................. 38

 

24.Метод наименьших квадратов для степенной, показательной, дробно-линейной, логарифмической,

 

гиперболической и дробно-рациональной приближающщих функций................................................................................ 39

 

25. Аппроксимация производных. Погрешность численного дифференцирования......................................................... 43

 

26.Использование интерполяционных формул.................................................................................................................................. 46

 

27. Аппроксимация частных производных............................................................................................................................................. 47

 

28.Уравнения в частных производных. Построение разностных схем. ТУРЧАК.................................................................. 51

 

1. Этапы решения прикладных задач. Машинное представление числа. Числа с плавающей точкой.

 

Процесс решения задачи с использованием ЭВМ включает, как правило, следующие этапы:

 

1. Математическая постановка задачи и построение математической модели. На данном этапе требуется

· определить, что дано, что надо получить;

· выделить наиболее существенные свойства изучаемого объекта;

 

· установить между ними количественные соотношения; Требования к математической модели:

 

· Математическая модель должна быть адекватной, т.е. правильно отражать действительность;

· Математическая модель не должна быть слишком сложной.

2. Алгоритмизация,т.е.

· Поиск метода решения задачи в рамках математической модели

 

· Разработка алгоритма (в виде словесного описания, математических формул, блок-схем).

 

3. Перевод алгоритма на язык программирования.

 

4. Исполнение программы на ЭВМ. В результате–получение результатоврешения.

 

5. Анализ полученных результатов. Полученные результаты сравниваются сожидаемыми, с данными, полученными экспериментальным путем.

 

Методы решения задачи делятся на
·	Точные:	·	Приближенные
аналитические	аналитические
·	графические	·	графические
		·	численные

 

Неустойчивость алгоритмов.

 

3. Структура полной погрешности эксперимента.

 

Погрешность возникает на ряде этапов решения задачи. Введем обозначения:

R –точное решение задачи(результат);

 

R – приближенное решение задачи;

ε – полная погрешность.

 

Полная погрешность e = R - R включает в себя:

 

· Погрешность исходных данных и математической модели. Возникает попричине неточности исходных данных и несоответствия построенной математической модели реальной ситуации. Таким образом, будет получен результат R₁≠R.

 

e ₁= R - R ₁

ε ₁–неустранимая погрешность.

 

· Погрешность метода. Возникает,если выбран приближенный(например,численный) метод. Таким образом, будет получен результат R₂≠R₁.

 

e ₂= R ₁- R ₂

ε₂ –устранимая погрешность.

 

· Погрешность вычислений: e ₃= R ₂- R ₃.

 

Таким образом, полная погрешность

 

Отделение корней

Метод Гаусса.

 

Метод Гаусса относится к точным методам, однако вычислительная ошибка присутствует всегда (ошибка округления и, возможно, ошибка исходных данных). Рассмотрим систему m линейных уравнений с n неизвестными:

ì a

x

+

a

x

+

...

+

a

x

=

b

ï 11

+

+

+

1 n

n

=

ï a 21 x 1

a 22 x 2

...

a 2 n xn

b 2

í......................

ï

ï a

x

+

a

m 2

x

+

...

+

a

mn

x

n

=

b

î

m 1 1

n

Алгоритм состоит из двух этапов.

I. Прямой ход – приведение матрицы к треугольному виду (сверху вниз):

ì x

+ a ¢

x

+

...

+

a ¢

x

n

=

b ¢

ï

1 n

ï

a ¢

x

+

...

+

a ¢

x

n

=

b ¢

2 n

í......................

ï

ï

xn

=

bn ¢

î

 

II. Обратный ход –определение неизвестных(снизу вверх).

 

Ручные вычисления по схеме единственного деления оформляют в виде таблицы с контролем вычислений, для чего в таблицу включены

· столбец контрольных сумм S,

· столбец сточных сумм S.

 

Контроль в прямом ходе:

 

· После внесения коэффициентов при неизвестных и свободных членов исходной системы находят контрольные суммы (суммы коэффициентов и свободных членов по строкам) и вносят их в столбец S.

 

· Далее, выполняя преобразования, над контрольными суммами производятся те же преобразования, что и над свободными членами.

 

· После выполнения каждого преобразования находят строчную сумму результатов и помещают ее в столбец S.

 

· При отсутствии вычислительных ошибок числа в столбцах S и S должны практически совпадать.

 

Контроль в обратном ходе:

При безошибочном выполнении вычислений в столбце S должны быть на единицу больше соответствующих значений неизвестных из столбца свободных членов Рассмотрим примеры решения СЛУ методом Гаусса

 

Разделы	x1		x2	x3	св чл	сумма	S
		3,25	14,52	-1,32	367,58	384,03
		32,02	-4,36	5,73	516,91	550,3
А		7,21	11,92	-41,46	-886,32	-908,65
			4,4677	-0,4062	113,1015	118,1631	118,163
			-147,4158	18,7365	-3104,6000	-3233,2825	-3233,2793
			-20,2921	-38,5313	-1701,7818	-1760,606	-1760,6052
А1				-0,1271	21,0602	21,9331	21,9331
				-41,1104	-1274,4261	-1315,5373	-1315,5365
А2					31,0001	32,0001	32,0001
					31,0001	32,0001
В					25,0003	26,0003
					13,9999

 

Решение систем линейных алгебраических уравнений. Требования к сходимости итерационного процесса.

Первая половина в билете №9.

Функцию r (x,y), определяющую расстояние между точками x и y множества X назовем метрикой, если

 

1) r (x,y)³0

2) r (x,y)=0 • x=y

3) r (x,y)= r (y,x)

4) r (x,y)£ r (x,z)+ r (z,y).

 

Множество X с введенной метрикой r назовем метрическим пространством. Последовательность точек метрического пространства называется фундаментальной,

 

если (" e > 0)($ N)(" m, n > N)[ r (x_m, x_n) < e ].

 

Пространство называется полным, если в нем любая фундаментальная последовательность сходится.

Отображение F пространства E в себя называется сжимающим, если

($ a, 0 < a <1)(" x, y Ï E)[ r (F (x), F (y)) £ a r (x, y)]

 

x – неподвижная точка, если F(x)=x.

Оценка расстояния между неподвижной точкой и приближением x ^(k) производится следующим образом:

r (x, x (k))£		a k	r (x (0), x (k))или r (x, x (k))£		a	r (x (k -1) , x (k)).
1 - a	1 - a

Таким образом, чтобы погрешность вычислений была меньше наперед заданного числа

ε, достаточно потребовать r (x (k -1), x (k))£ e	1 - a	.
							a
Рассмотрим 3 типа метрики.
Пусть x(x1,x2,…,xn) и y(y1,y2,…,yn) – две точки n -мерного пространства.
I. r 1 (x, y) = max		xi	- yi		Максимальная из сумм модулей коэффициентов при неизвестных в
	1£ i £ n
правой	части	системы, взятых по	строкам, должна быть меньше единицы:
	n
a 1 = max1£ i £ n	å aij <1

j =1

 

n

II. r ₂₁ (x, y) = å x_i - y_i Максимальная из сумм модулей коэффициентов при неизвестных

i =1

 

в

правой части

системы,

взятых

по столбцам, должна быть

меньше

единицы:

n

a 2

= max1£ j £ n

å

aij

< 1

i =1

III. r 3 (x, y) =

n

- yi)2Корень квадратный из суммы квадратов коэффициентов при

å(xi

i =1

неизвестных

в

правой

части

системы, должен быть

меньше

единицы:

n

n

a 3=å å aij 2¹1<1

i =1

j =1

 

СЛУ преобразуется таким образом, чтобы по одной из метрик выполнялось α < 1.

ì x

= a

x

+

a

x

+

...

+

a

x

+

b

ï 1

1 n

n

ï x 2

= a 21 x 1

+

a 22 x 2

+

...

+

a 2 n xn

+

b 2

í......................

ï

ï x

n

= a

x

+

a

m 2

x

+

...

+

a

mn

x

n

=

b

n

î

m 1 1

При этом СЛУ задает отображение, которое при α < 1 будет сжимающим. Значит, взяв любую точку в качестве начального приближения, получим последовательность точек, которая будет сходиться к неподвижной точке; это точка и будет решением системы. Чтобы привести СЛУ к итерационному виду нужно:

 

1) с помощью равносильных преобразований привести систему к виду с преобладающими диагональными коэффициентами (по абсолютной величине);

 

2) разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным единице.

 

Если для этой системы α < 1, то система задает сжимающее отображение.

 

11. Оценка погрешности метода простой итерации. x=Bx+d;

Пусть ||B||<1, имеем:

x*=Bx*+d;

_x(k)_=Bx(k-1)_{+d ;}

x*=x^(k)+B(x*–x^(k-1));

Вычтем из каждой части x^(k-1):

_x*–x(k-1)_=x(k)_–x(k-1)_+B(x*–x(k-1)_{) ;}

||x*–x^(k-1)||≤

||x^(k)–x^(k-1)||+||B||•||x*–x^(k-1)||;

||x*–x^(k-1)||•(1–||B||)≤

||x^(k)–x^(k-1)||;

||x*–x^(k-1)||≤

||x^(k)–x^(k-1)||/(1–||B||);

Кроме того:

||x*–x^(k)||≤||B||•||x*–x^(k-1)||;

 

||x*–x^(k)||≤(||B||/(1–||B||))•||x^(k)–x^(k-1)||; (1)–Разность между точным решением и k -ымприближением.

Пусть требуется найти решение с точностью ε. Из (1) имеем:

(||B||/(1–||B||))•||x^(k)–x^(k-1)||<ε;

Достаточно выполнение условия:

 

||x^(k)–x^(k-1)||≤((1–||B||)•ε)/||B||;–критерий выхода.

 

Метод Зейделя

 

При решении СЛУ методом простой итерации каждый шаг итерационного процесса состоит в переходе от уже имеющегося приближения значений неизвестных к новому приближению.

 

Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении значений y_i учитываются уже полученные значения y₁, y₂,…,y_i-

 

1.

I. Условие α<1 является достаточным для сходимости итерационного процесса метода Зейделя. Причем метод Зейделя обеспечивает более быструю сходимость, чем метод простой итерации.

 

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв за основу метод итерации)

 

program slu_zejdel1;

 

{ *** с использованием евклидовой метрики *** } var p,b,x1,x2,x3,y1,y2,y3,a,e: real;

 

N: integer;

begin

write('Введите x1, x2, x3: '); readln(x1,x2,x3);

write('Введите A, E: '); readln(a,e);

b:=e*(1-a)/a;

 

N:=0; {число итераций}

repeat

N:=N+1;

 

y1:= 0.1362*x2-0.1790*x3+16.1433;

y2:=-0.2238*y1+0.0909*x3+25.3154;

y3:= 0.1739*y1+0.2875*y2+21.3777;

p:=sqrt(sqr(x1-y1)+sqr(x2-y2)+sqr(x3-y3));

x1:=y1; x2:=y2; x3:=y3;

until p<=b;

writeln('x1 = ',x1:8:6);

writeln('x2 = ',x2:8:6);

writeln('x3 = ',x3:8:6);

writeln('Число итераций - N = ',N);

 

readln

end.

 

Введите x1, x2, x3: 0 0 0

Введите A, E: 0.2218 0.0001

x1 = 13.999370

 

x2 = 25.000219

x3 = 30.999753

Число итераций - N=6

 

Как видно из примера, по сравнению с методом итераций решение получено за меньшее количество шагов.

 

II. Рассмотрим практическую схему преобразования исходной СЛУ, гарантирующую сходимость метода Зейделя.

Пусть система записана в матричной форме: Ax=b.

Умножим левую и правую части слева на матрицу A^T: A^TAx= A^T b.

Обозначим: A^TA=C, A^T b=d.

 

Преобразованная система станет иметь вид: Cx=d. Такую систему называют нормальной:

· матрица C является симметричной;

 

· все элементы главной диагонали матрицы C положительны. Нормальную систему легко привести к виду:

xi =å aij x j

+ b j,

(i = 1,2,¼, n), где ai = -

cij

(j ¹ i)

и bi

=

di

.

cii

j ¹ i

cii

Вычислительные формулы имеют вид:

ì

n

ï y 1 = å a 1 j x j + b 1

ï

j =1

ï

n

ï y 2

= a 21 y 1 + å a 2 j x j + b 2

ï

j =1

ï

ï...

í

i -1

n

ï

=å aij y j +å aij x j + bi

ï yi

ï

j =1

j = i

ï...

ï

n -1

ï yn =å anj y j + ann xn + bn

î

ï

j =1

Рассмотрим на примере.

æ 3,25

14,52

-1,32 ö

æ

367,58

ö

æ 3,25

32,02

7,21

ö

ç

- 4,36

÷

ç

÷

ç

- 4,36

÷

A = ç

32,02

5,73

÷

b = ç

516,91

÷

AT = ç

14,52

11,92

÷

ç

7,21

11,92

- 41,46

÷

ç

- 886,32

÷

ç

-1,32

5,73

- 41,46

÷

è

ø

è

ø

è

ø

æ

1087,827

- 6,474

-119,742 ö

æ

11355,726 ö

ç

- 6,474

- 538,3524

÷

D =

ç

- 7481,4004

÷

C = AT A = ç

371,9264

÷

AT b = ç

÷

ç

-119,742

- 538,3524

1753,5069

÷

ç

39223,5159

÷

è

ø

è

ø

После деления на диагональные элементы получим:

æ		- 0,0060	- 0,1101ö	æ	10,4389 ö
ç	- 0,0174		-1,4475	÷	ç		÷
a = ç		÷	b = ç	- 20,1153÷
ç	- 0,0683	- 0,3070		÷	ç	22,3686	÷
è	ø	è	ø

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, r 1 (x, y) = max xi - yi).

1£ i £ n

 

program slu_zejdel2;

var x1,y1,x2,y2,x3,y3,e,a,b,c: real;

N: integer;

begin

 

write('Введите X1, X2, X3 - '); readln(x1,x2,x3); write('Введите погрешность Е - '); readln(e); N:=0; {число итераций}

 

repeat

N:=N+1;

y1:= 0.0060*x2+0.1101*x3+10.4389;

y2:= 0.0174*y1+1.4475*x3-20.1153;

y3:= 0.0683*y1+0.3070*y2+22.3686;

 

a:=abs(y1-x1); b:=abs(y2-x2); c:=abs(y3-x3);

if a<b then a:=b;

 

if a<c then a:=c;

x1:=y1; x2:=y2; x3:=y3;

until a<=e;

writeln('X1 = ',x1:11:8);

writeln('X2 = ',x2:11:8);

writeln('X3 = ',x3:11:8);

 

writeln('Число итераций - N = ',N);

readln

end.

 

Введите X1, X2, X3 - 0 0 0

Введите погрешность Е -.0001

X1 = 14.00204110

 

X2 = 25.00128107

X3 = 31.00033269

Число итераций - N = 18

 

Решением

 

 

Дифференциального

 

 

Уравнения

 

(1)

 

(1) называется функция

 

 

y(x),

 

подстановка которой в уравнение обращает его в тождество: y ¢(x) = f (x, y (x)).

 

График решения y=y(x) называется интегральной кривой.

 

Задача Коши для дифференциального уравнения(1)состоит в том,чтобы найтирешение дифференциального уравнения (1), удовлетворяющее начальному условию y(x₀)=y₀ (2).Пару чисел (x₀,y₀) называют начальными данными.

 

Решение задачи Коши называется частным решением дифференциальногоуравнения (1)при условии(2).

 

Геометрически задача Коши означает, что требуется найти интегральную кривую y=y(x),проходящую через заданную точку (x₀,y₀).

Теорема о существовании и единственности решения задачи Коши.

 

Пусть функция f(x,y) – правая ч