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

Содержание

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

+

+

+

1n

n

=

ïa21x1

a22 x2

...

a2n xn

b2

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

ï

ïa

x

+

a

m2

x

+

...

+

a

mn

x

n

=

b

î

m1 1

n

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

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

ìx

+ a¢

x

+

...

+

a¢

x

n

=

b¢

ï

1n

ï

a¢

x

+

...

+

a¢

x

n

=

b¢

2n

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

ï

ï

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. r1 (x, y) = max		xi	- yi		Максимальная из сумм модулей коэффициентов при неизвестных в
	1£i£n
правой	части	системы, взятых по	строкам, должна быть меньше единицы:
	n
a1 = max1£i£n	å aij <1

j=1

n

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

i=1

в

правой части

системы,

взятых

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

меньше

единицы:

n

a2

= max1£j£n

å

aij

< 1

i=1

III. r3 (x, y) =

n

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

å(xi

i=1

неизвестных

в

правой

части

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

меньше

единицы:

n

n

a3=å åaij2¹1<1

i=1

j =1

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

ìx

= a

x

+

a

x

+

...

+

a

x

+

b

ï 1

1n

n

ïx2

= a21x1

+

a22 x2

+

...

+

a2n xn

+

b2

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

ï

ïx

n

= a

x

+

a

m2

x

+

...

+

a

mn

x

n

=

b

n

î

m1 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

ïy1 = åa1 j x j + b1

ï

j =1

ï

n

ïy2

= a21 y1 + åa2 j x j + b2

ï

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	÷
è	ø	è	ø

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, r1 (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) – правая ч