WinNavigator

Frigate

Norton Commander

WinNC

Dos Navigator

Servant Salamander

Turbo Browser

Winamp, Skins, Plugins

Необходимые Утилиты

Текстовые редакторы

Юмор

File managers and best utilites

Реферат: Численные методы. Реферат численные методы

Реферат: Численные методы

ЛЕКЦИЯ №1

Численные методы представляют собой набор алгоритмов, позволяющих получать приближенное (численное) решение математических задач.

Погрешности, возникающие при решении задач, бывают двух видов:

1)абсолютная

p - p , где p - точное значение, p - не точное.

2)относительная

Эмпирические данные:

Погрешности Случайные Ошибки

измерительного помехи набора

прибора

1) Нахождение нулей функции;

2) Системы линейных и нелинейных уравнений;

3) Приближение функции. Интерполяция. Экстраполяция.

4) Решение дифференциальных уравнений.

5) Расчет собственных значений и собственных векторов матриц.

НАХОЖДЕНИЕ НУЛЕЙ ФУНКЦИИ

Общая постановка задачи

Дана некоторая функция f(х). Необходимо найти хотя бы одно значение х, при котором f(х)=0.

Этапы:

1) Отделение корней.

Область определения функции разбивается на отрезки, на каждом из которых

содержится единственный корень функции.

2) Уточнение корня при помощи одного из численных методов на каждом из выбранных отрезков.

Нуль функции – точка пересечения графика функции с осью Ох.

Непрерывность f(х) в точке х0:

Производная функции: f' =

Физический смысл: f'(х0)- скорость

Геометрический смысл: f'(х0)-тангенс угла наклонной касательной к графику функции, проведенной в данной точке.

Если функция дифференцируема в точке, то она непрерывна. Обратное не верно.

Предел функции в точке:

x: | x-x0| <

ε >0 (ε)

| f(x) – A| < ε

Градиент функции – это вектор.

Геометрический смысл : показывает направление локального возрастания функции в данной точке .

1) Наблюдаем смену знака функции.

2) Исследуем функцию на монотонность.

Теорема №1: если функция f(x) непрерывна на отрезке [a, b] и в концах отрезка принимает значения разных знаков, то на этом отрезке функция имеет хотя бы один корень.

f(x) C[a, b]

f(a) * f(b) < 0 → [a, b] f()=0

Теорема№2: если функция непрерывна и монотонна на отрезке и в концах отрезка принимает значения разных знаков, то на этом отрезке существует только единственный корень функции.

f(x) C[a, b], f ( ) и f(a) * f(b) < 0→[a, b] f() = 0

МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ

Дано: f(x) непрерывна на [a,b], на [a,b] существует динственный корень f(x)=0, ε

1) Делим отрезок пополам. Получаем точку

с= (b + a)/2.

Если f(a) * f(c) < 0,то b:=c.

Если f(b) * f(c) < 0,то а:=с

2) Продолжаем делить [a, b] на 2, пока|b-a| > ε, где ε- заданная точность.

ЛЕКЦИЯ №2

МЕТОД ХОРД

Дано: 1) f(x) C''[a, b]

2) f(a) * f(b) < 0

3) f'(x) и f''(x) знакопостоянна на отрезке [a, b].

4) ε, чтобы получить f(x)=0

1) f(b) 2)

f'(x) >

0 f'(x) > 0

f''(x) >

0 f''(x) < 0

f(a) a x

3) 4)

f'(x)

<0 f'(x) <0

f''(x)

<0 f''(x) > 0

(2.1)

x1(x1,f(x1))

b – неподвижный конец отрезка.

Для случаев 1), 3)

Для случаев 2), 4)

Можем ввести некоторую с:

(2.2)

(2.3)

Алгоритм:

1) Вычисляем неподвижный конец отрезка секущих по формуле(2.3)

2) Находим первое приближение к корню по формуле (2.1)

3) Находим первое приближение к корню по формуле (2.2) до тех пор, пока модуль разности двух последних приближений не станет меньше заданной точности. В этом случае, значением корня является последнее приближение.

МЕТОД КАСАТЕЛЬНЫХ

Дано: 1) f(x) C''[a, b];

2) f(a)*f(b) < 0;

3) f'(x) и f''(x) знакопостоянны на [a, b];

4) ε, чтобы решить уравнение f(x)=0

т. х0

y=f(x0)+f'(x0)(x-x0) –

уравнение касательной

a x2 x1 b

y=f(b)+f’(b)*(x-b)

(x1,0) : 0= f(b)+ f’(b)(x1-b)

x1=

x2=

xn+1= (2.4)

Второй подход (метод Ньютона):

-приближение

0 = f() = f(xn+hn) ≈ f(xn)+f'(xn)*hn

x0 = начальное приближение (2.5)

Алгоритм:

1) По формуле (2.5) находим первое приближение к корню х0 (начальное)

2) По формуле (2.4) находим последующее приближение к корню до тех пор, пока модуль разности двух последних приближений не станет заданной точности. В этом случае корень равен последнему приближению.

МЕТОД ИТЕРАЦИЙ

Дано: 1) f(x)C''[a,b]

2)f(a)*f(b)<0

3)f'(x) знакопостоянна

4)ε, f(x)=0

Уравнение f(x)=0 заменяется уравнением вида x=φ(x)

φ(x)=x-f(x)*C (2.6)

Пока |xn+1-xn|<ε

φ' >0

Cтроим последователь

Выбираем

Находим значение функции

x2= φ(x1), x3= φ(x2)

xn+1= φ(xn) (2.7)

Точка ε, для которой выполняется ε=f(ε), называется неподвижной точкой метода итераций. Очевидно, что эта точка является корнем уравнения f(x)=0.

φ(ε) ε -f(x)* ε

0 f(ε)*C

f(ε) 0

Достаточное условие: для того, чтобы метод итераций сходился достаточно чтобы:

1) φ(x) (2.8) - Функция является непрерывной и дифференцируемой на [a,b].

2) φ(x) значения - является необходимым условием

3) |φ(x)|<1 для всех

Константа С в формуле(2.6) подбирается таким образом, чтобы функция

φ(x) удовлетворяла условиям сходимости метода итераций.

Скорость сходимости метода Ньютона (касательных) выше сходимости метода секущих (хорд).

ЛЕКЦИЯ №3

МЕТОДЫ РЕШЕНИЯ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Общий вид алгебраического уравнения:

а0хn+ а1хn+1+…+ аn-1х+an=0, a00 (3.1)

n=1: а0х+a1=0, x=

n=2: а0х2+a1x+a2=0, x1,2=

Алгебраическое уравнение n- степени имеет ровно n корней.

Теорема Виета (обобщенная):

xn+xn-1+…+x+=0

x1+x2+…+xn=-; (3.2)

x1x2+x1x3+…+xn-1xn=;

x1x2x3…xn=(-1);

Пусть все корни уравнения (3.1) действительны, различны и удовлетворяют соотношениям:

|x1|>>|x2|>>…>>|xn| (3.3)

Преобразуем:

x1(1++…+)= x1=-; (3.4)

Подставим (3.4) : х2=- продолжая получим общую формулу

хk=-, k=1,n (3.5)

Корни уравнения, удовлетворяющие соотношения(3.3), называются отдельными. Задача состоит в том, чтобы по исходному уравнению построить такое уравнение, корни которого будут отделены.

yi=-xim

b0yn + b1yn-1+…+ bn-1y+bn=0 (3.6)

|x1|>|x2|>…>|xn|

Решив уравнение (3.6), корни которого являются отдельными, получим уравнения y1…yn

, i=2,n

Значит |yi-1|>>|xi|

МЕТОД ЛОБАЧЕВСКОГО

Для отделения корней Лобачевский предложил метод квадратирования - способ построения по исходному уравнению нового уравнения, кони которого связаны с корнями исходного следующим образом:

yi=-xi2 (3.7)

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

b0(m)yn + b1(m)yn-1+…+ bn-1(m)y+ bn(m)=0 (3.8)

Пусть уравнение (3.8) получено в результате m-го шага квадрирования.

m=1 b0(1)=a02, b1(1)= a12=2 a0 a2

bk(1)=ak2-2ak-1ak+1+2ak-2ak+2….,k=0,n

При получении bk коэффициента , который рассчитывается как квадрат соответствующего коэффициента ak минус удвоенное произведение соседних коэффициентов с ak плюс удвоенное произведение следующей пары соседей , чередуя знаки, пока в число соседних коэффициентов не попадут а0 и аn.

m>1b0(m)=( b0(m-1))2, b1(m)=( b1(m-1))2-2b0(m-1)b2(m-1) (3.9)

bk(m)=( b0(m-1))2-2bk-1(m-1)bk-1(m-1)+2bk-2(m-1)bk+2(m-1)

Критерий остановки: bk(m)≈( b0(m-1))2, k=0,n (3.10)

Получим корень: yi(m)=-xi2, i=1,n (3.11)

(3.11)-связь корней, полученных на m-шаге процесса квадрирования с корнями исходного уравнения.

yi на m-шаге : , отсюда

, i=1,n (3.12)

Знак xi определяется путем подстановки в исходное уравнение. Те коэффициенты, которые будут отвечать за наличие комплексных корней, имеют следующий признак: один или несколько коэффициентов в ходе процесса квадрирования ведут себя неправильно (все остальные коэффициенты →к квадратам предыдущих, а неправильные →к квадратам предыдущих могут менять знак).

Признак наличия кратных корней: один или несколько коэффициентов → к половине квадрата коэффициента предыдущего шага.

МЕТОДЫ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

СЛАУ

Методы решения СЛАУ делятся на точные и приближенные. К точным методам относятся метод Гаусса, метод Крамера, метод обратной матрицы .

Существуют приближенные методы: метод итераций, Зейделя и т.д.

Общий вид СЛАУ:

(3.13)

Сколько переменных столько и ограничений на них.

пересечение прямых (точка)

пересечение плоскостей (прямая)

точка пересечения трех плоскостей

Т.о. геометрический смысл решения СЛАУ – точка пересечения гиперплоскостей в n-мерном пространстве.

Матрица :=А; B=; X=;

Cn*k*Dk*m=Zn*m , An*n*Bn*1=Xn*1 AX=B (3.14)

ЛЕКЦИЯ №4

МЕТОД ГАУССА

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

1 шаг: Выбираем в матрице А максимальный элемент по всем строкам и столбцам. Путем перестановки строк и столбцов ставим этот элемент на место а11. Теперь а11- главный элемент.

А→А1→А2→…→Аn

Аn должна будет содержать ниже главной диагонали все нули.

, j =1,n ; b1 =b1/a11

Получим систему вида

, i=2,n , j=1,n

Получим А' х=В' и систему

Пусть а221 – максимальный по модулю элемент матрицы А1 по строкам i≥2 и столбцам j≥2. Если это не так, то добиваемся этого путем перестановки строк и столбцов.

А2:

В2: b12=b11; b22=b21/a221; bi2=bi1-b22-b22ai21

Пусть акк+1 максимальный по модулю элемент матрицы Ак, i≥k, j≥k.

Пусть на некотором шаге k<n элемент =0, матрица Вк имеет ∞ множество решений. Причем корни х1,…хк являются зависимыми, а корни хк+1,….xn – независимые.

Если хотя бы один элемент bik при i≥k+1 ¹ 0, то решения у системы нет.

Если была получена матрица Аn, то система имеет единственное решение.

Начинается обратный ход метода Гаусса.

Определитель : det A=

det A==a11a22-a12a21

Минор Hij элемента матрицы aij представляет собой определитель, полученный из матрицы А путем вычеркивания i cтроки и j столбца.

Алгебраическое дополнение Аij элемента аij называется число, равное

Аij=(-1)i+j*Mij

Способы вычисления определителей

1. Привести определитель к треугольному виду (ниже главной диагонали все элементы=0). Достичь этого можно путем вычитания (сложения) строк определителя, умноженных на некоторое число. При перестановки строк/столбцов знак определителя меняется на противоположный. Определитель треугольного вида равен произведению элементов главной диагонали.

2. Рекуррентный способ основан на том, что определитель равен сумме произведений элементов строки/столбца на их алгебраические дополнения. Т.о. задача вычисления определителя n-го порядка сводится к вычислению n определителей n-1 порядка.

Наиболее целесообразно раскладывать определитель по той строке/столбцу, которая содержит максимальное количество нулей. Алгебраическое дополнение 0-го элемента можно не вычислять.

Пусть дана система уравнений вида Ах=В

Если определитель А=0, то система может решений не иметь, либо иметь бесконечное множество решений.

Если определитель А≠0, то корни системы могут быть найдены следующим образом.

Пусть Ак-матрица, полученная из матрицы А путем замен к-го столбца на матрицу-столбец В. Тогда решение .

МЕТОД ОБРАТНОЙ МАТРИЦЫ

Пусть дана система Ах=В и detA≠0.

Умножим обе части системы на А-1:

А-1*Ах=А-1*В→х=А-1*В

Способы нахождения обратной матрицы:

1. Способ основан на методе Гаусса.

Записать матрицу А, а рядом с ней единичную матрицу. Выполняя элементарные преобразования матрицы А, параллельно выполнять те же преобразования над единичной матрицей. Как только матрица А превратилась в единичную на месте исходной единичной матрицы будет обратная к матрице А.

2. Через алгебраические дополнения.

Составить матрицу алгебраических дополнений, в которой на месте aij элементов будут находиться Aij.

Разделить каждый элемент матрицы алгебраических дополнений на detA.

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

www.referatmix.ru

Реферат - Численные методы - Разное

ЧИСЛЕННЫЕ МЕТОДЫ

акад. РАН Н.С. Бахвалов

1 год, 4 курс, отделение математики

1. Предмет теории численных методов.

2. Классификация погрешностей.

3. Запись чисел в ЭВМ. Абсолютная и относительная погрешности. Погрешность функции.

Численные методы анализа.

4. Постановка задачи интерполирования. Интерполяционный многочлен Лагранжа, оценка остаточного члена.

5. Уравнения в конечных разностях.

6. Многочлены Чебышева и их свойства.

7. Минимизация погрешности остаточного члена интерполяционной формулы.

8. Разделенные разности и их свойства.

9. Интерполяционный многочлен с разделенными разностями.

10. Численное дифференцирование. Примеры построения формул численного дифференцирования.

11. Вычислительная погрешность формул численного дифференцирования.

12. Простейшие квадратурные формулы. Составная формула трапеций.

13. Понятие об ортогональных многочленах. Квадратуры Гаусса и оценка их погрешности.

14. Постановка задач оптимизации.

15. Оптимизация распределения узлов составной квадратурной формулы трапеций.

16. Интегрирование быстроосциллирующих функций и функций с особенностями.

17. Главный член погрешности численного интегрирования. Правило Рунге практической оценки погрешности.

18. Теорема о существовании элемента наилучшего приближения в линейном нормированном пространстве.

19. Теорема Валле-Пуссена.

20. Теорема Чебышева.

21. Единственность многочлена наилучшего равномерного приближения.

22. Примеры наилучшего равномерного приближения.

23. Дискретное преобразование Фурье. Быстрое преобразование Фурье.

24. Интерполяция и приближение сплайнами.

25. Оценка погрешности повторного численного интегрирования по равномерной сетке.

26. Оценка снизу погрешности численного дифференцирования на классах функций.

Численные методы линейной алгебры.

27. Нормы матриц. Метод Гаусса решения систем линейных уравнений.

28. Метод вращений решения систем линейных уравнений.

29. Метод простой итерации решения систем линейных уравнений.

30. -процесс практической оценки погрешности и ускорения сходимости.

31. Оптимальный одношаговый итерационный процесс. Ускорение сходимости с использованием многочленов Чебышева.

32. Метод наискорейшего градиентного спуска.

33. Итерационные методы с использованием спектрально эквивалентных операторов.

34. Понятие о методе Зейделя.

35. Решение частичной проблемы собственных значений.

36. Обусловленность систем уравнений и матриц.

Численные методы решения нелинейных систем и задач минимизации.

37. Метод Ньютона решения нелинейных задач.

38. Решение стационарных задач путем установления.

Численные методы решения задачи Коши

для обыкновенных дифференциальных уравнений.

39. Методы Эйлера и Рунге-Кутта решения задачи Коши.

40. Оценка глобальной погрешности метода Эйлера.

41. Жесткие системы дифференциальных уравнений. Метод Ракитского.

42. Метод Розенброка.

43. Метод Лебедева.

Численные методы решения краевой задачи

для обыкновенных дифференциальных уравнений.

44. Оценка погрешности простейшего метода решения краевой задачи для дифференциального уравнения второго порядка.

45. Метод Ритца решения краевой задачи для дифференциального уравнения второго порядка и его вариационно-разностный вариант.

46. Метод Бубнова-Галеркина решения краевой задачи для дифференциального уравнения второго порядка и его вариационно-разностный вариант.

47. Метод дискретной аппроксимации минимизируемого функционала.

48. Оценка погрешности решения краевой задачи для дифференциального уравнения второго порядка вариационно-разностным методом.

49. Метод стрельбы решения краевой задачи.

50. Метод прогонки решения краевой задачи.

51. Два варианта метода Ньютона решения краевой задачи для нелинейного дифференциального уравнения второго порядка.

Численные методы решения уравнений с частными производными.

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

53. Определения аппроксимации, корректности, сходимости. Теорема Филиппова о связи аппроксимации, корректности и сходимости.

54. Спектральный признак устойчивости. Примеры его применения для исследования разностных методов задачи Коши для гиперболического уравнения.

55. Принцип замороженных коэффициентов.

56. Примеры применения спектрального признака устойчивости для исследования явной и неявной разностной аппроксимации уравнения теплопроводности.

57. Исследование устойчивости явной и неявной разностной аппроксимации уравнения теплопроводности в равномерной метрике.

58. Экономичная схема решения двумерного уравнения теплопроводности.

59. Оценка погрешности разностной аппроксимации уравнения Пуассона.

60. Понятие об итерационном методе Федоренко решения краевых задач.

Интегральные уравнения и некорректные задачи.

61. Интегральные уравнения Фредгольма первого рода. Метод регуляризации по Тихонову.

Литература

1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. Москва – Санкт-Петербург, Физматлит, 2000.

www.ronl.ru

Реферат - Сравнительный анализ численных методов Численные методы

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра ____САПР______

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

По дисциплине: ”Математическое обеспечение САПР"

Тема: «Сравнительный анализ численных методов»

Руководитель

(подпись) (дата)

Студент

(подпись) (дата)

2009

Содержание

Введение

1. Постановка задачи

2. Методы решения нелинейных уравнений

2.1 Общие сведения

2.2 Метод касательных (метод Ньютона)

2.2.1 Общие сведения

2.2.2 Решение нелинейного уравнения методом касательных

2.3 Метод хорд

2.3.1 Общие сведения

2.3.2 Решение нелинейного уравнения методом хорд

2.4 Вывод

2.5 Метод простых итераций

2.5.1 Общие сведения

2.5.2 Решение нелинейного уравнения методом простых итераций

2.6 Программа для решения нелинейных уравнений

3. Решение нелинейных уравнений методом интерполирования

3.1 Интерполяция

3.2 Многочлен Лагранжа

3.3 Интерполяция сплайнами

3.4 Использование интерполяции на практике

3.4.1 Интерполяция с помощью многочлена Лагранжа

3.4.2 Обратная интерполяция

3.4.3 Интерполяция сплайнами

3.5 Программа для использования интерполяции

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

4.1 Общие сведения

4.2 Метод простой итерации

4.2.1 Описание метода

4.2.2 Решение СЛАУ методом простых итераций

4.2.3 Программа для решения СЛАУ методом простых итераций

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

4.3.1 Описание метода

4.3.2 Решение СЛАУ методом Зейделя

4.3.3 Программа дл решения СЛАУ методом Зейделя

4.4 Сравнительный анализ

5. Сравнительный анализ различных методов численного дифференцирования и интегрирования

5.1 Методы численного дифференцирования

5.1.1 Описание метода

5.1.2 Нахождение производной

5.2 Методы численного интегрирования

5.2.1 Общие сведения

5.2.2 Нахождение определенного интеграла

5.3 Решение ОДУ

5.3.1 Решение ОДУ методом Эйлера

5.3.2 Решение ОДУ методом Рунге-Кутты

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

6.1 Общие сведения

6.2 Метод Эйлера

Заключение

Список использованной литературы

Введение

На практике в большинстве случаев найти точное решение возникшей математической задачи не удается. Это происходит главным образом не потому, что мы не умеем этого сделать, а поскольку искомое решение обычно не выражается в привычных для нас элементарных или других известных функциях. Поэтому важное значение приобрели численные методы, особенно в связи с возрастанием роли математических методов в различных областях науки и техники и с появлением высокопроизводительных ЭВМ.

Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет ЭВМ.

В настоящее время появилось значительное число различных программных продуктов (MathCAD, MathLAB и т.д.), с помощью которых, задавая только входные данные, можно решить значительное число задач.

Конечно, использование таких программных продуктов значительно сокращает время и ресурсы по решению ряда важных задач. Однако, использование этих программ без тщательного анализа метода, с помощью которого решается задача, нельзя гарантировать, что задача решена правильно. Поэтому для более полного понимания того, как осуществляется расчет различного вида уравнений и их систем, необходимо теоретически изучить методы их решения и на практике их проработать.

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

1. Постановка задачи

Порядок выполнения:

По итерационным методам решения нелинейных уравнений:

Определить корень в заданном или любом выбранном отрезке методом хорд, касательных, простых итераций.

Используя результаты решений, указать наименьший полученный отрезок, в котором содержится корень уравнения.

Для каждого метода и каждой задачи построить график функции />на [a,b] и убедиться в выполнении условия сходимости итерационной процедуры.

Используя функции f(x) из п.1, построить интерполяционный многочлен L4 (x) на [a,b], использовав в качестве узловых aиb, остальные необходимые узловые точки выбрать, разделив промежуток [a,b] на почти равные части. Вычислить значения f (x) и L4 (x) в двух точках, одна из которых — середина крайней части, а вторая — середина части, содержащей точку />. Сравнить полученные величины. Используя эти же узловые точки, провести обратную интерполяцию и определить значение х при y=0. Полученный результат сравнить с ранее найденным решением уравнения.

Сравнить результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации.

Провести сравнительный анализ различных методов численного дифференцирования и интегрирования.

Найти численное решение обыкновенного дифференциального уравнения методом Эйлера и уточненным методом Эйлера с 5-ю и 20-ю шагами и сравнить их, если возможно с результатом точного решения ОДУ.

2. Методы решения нелинейных уравнений

2.1 Общие сведения

Рассмотрим уравнение вида f (x) =0, (2.1), где f (x) — любая нелинейная функция.

Корнем уравнения(2.1) называется значение />, при котором/>. Способы приближенного решения, т.е. алгоритм решения, предполагает определение x* c некоторой наперед заданной точностью.

Для нахождения корней уравнения (2.1) различают следующие два этапа.

Отделения (локализации) корней, т.е. нахождение таких интервалов по аргументу x, внутри каждого из которых существует только один корень уравнения (2.1). Если у функции на концах исследуемого отрезка [a,b] функция имеет разные знаки, то на этом отрезке функция имеет не менее одного корня. Если же одинаковые знаки, то функция может не иметь корней или иметь четное число корней. Следовательно, локализация заключается в том, что необходимо установить отрезки, на которых есть смена знаков функции и, кроме того, выполнено условие единственности корня, т.е. функция на этом отрезке должна иметь первую производную с постоянным знаком. Из условия сходимости итерационной последовательности также требуется, чтобы вторая производная не меняла знак, т.е. на исследуемом отрезке функция бала бы только выпуклой или вогнутой.

Уточнение корней заключается в применении некоторого итерационного метода, в результате которого корень уравнения (2.1) может быть получен с любой наперед заданной точностью ε. При этом, останавливая процесс на какой-либо конечной итерации, необходимо оценить погрешность по сравнению с точным корнем, который неизвестен. Выбранный метод позволяет построить последовательность х1, х2, х3, …, хk, … приближений к корню. Итерационный процесс состоит в последовательном уточнении начального приближения х0. Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня х1, х2, х3, …, хk, … Если эти значения с ростом k стремятся к истинному значению корня />, то итерационный процесс сходится.

Основными методами решения нелинейных уравнений, реализованных в виде численной процедуры, являются итерационные методы.

2.2 Метод касательных (метод Ньютона)

2.2.1 Общие сведения

Метод Ньютона, называемый также методом касательных, состоит в следующем. Рассмотрим в точке x0касательную к кривой y=f (x), задаваемую уравнением

y= f (x0) + (x-x0) f ’ (x0).

За начальное приближение x0 принимается один из концов отрезка [a, b], где значение функции имеет такой же знак, что и 2-я производная. Функция f (x) должна удовлетворять на отрезке [a, b] следующим условиям:

1) существование производных 1-го и 2-го порядков;

2) f ’ (x) />0;

3) производные 1-го и 2-го порядков знакопостоянны на отрезке [a, b].

Положим y=0, находим точку x1 пересечения касательной с осью абсцисс:

x1= х0 — f (х0) /f ’ (х0).

Построив касательную в точке x1 (рисунок 2.1), получаем по аналогичной формуле точку x2 пересечения этой касательной с осью x и т.д. Формула для n-го приближения имеет вид:

хn=хn-1 — F (хn-1) /F’ (хn-1), n=1,2,…

--PAGE_BREAK--

Рисунок 2.1 — Метод касательных

В этом методе на n-й итерации проводится касательная к кривой y =f (x) при х=xn-1 и ищется точка пересечения касательной с точкой абсцисс. При этом необязательно задавать отрезок [a,b], содержащий корень уравнения, а достаточно лишь найти некоторое начальное приближение корня х.

Итерационный процесс останавливают при выполнении условия />; где ε — заданная точность.

2.2.2 Решение нелинейного уравнения методом касательных

1. Дано уравнение tg (0.36*x +0.4) =x2. Решить его методом касательных с точностью решения/>=0,001.

Для нахождения корня исследуем функцию

/>.

График функции представлен на рисунке 2.2

Рисунок 2.2 — График исследуемой функции

Находим отрезок, в котором функция монотонно возрастает или убывает, а также где концы отрезка будут иметь разные знаки.

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.3

Рисунок 2.3 — График функции на выбранном отрезке

Проверяем существование корня на отрезке по условию />

f (-1) = — 0,95998

f (0) =0,42279

0,405869<0, следовательно, на данном промежутке корень есть.

Исследуем функцию на монотонность: />

Экстремумов на выбранном отрезке нет.

Находим первую производную функции:

В точке aпервая и вторая производные равны:

/>, />

В точке bпервая и вторая производные равны:

/>,/>

Выбираем тот конец отрезка, который совпадает со знаком 2-ой производной.

/>, x0=-1, />-0,95998* (/>) =1,90998;/>

По формуле

находим:

/>, />, />x>0.001

/>/>/>

/>x>0.001

/>/>

/>x>0.001

/>, />

/>x<0.001

Необходимая точность достигнута при n=4, т.е. на 4-й итерации.

Так как заданная точность достигнута, то процесс можно прекратить.

Теперь строим график функции x=/>, т.е. последовательность xn,стремящаяся к x*и условием сходимости здесь является /> (рисунок 2.4).

Рисунок 2.4 — График функции /> для исследуемой функции

2. Дано уравнение

x3-0,2x2+0,4x-1,4=0.

Решить его методом касательных с точностью решения/>=0,001.

Для нахождения корня исследуем функцию

/>.

График функции представлен на рисунке 2.5

Рисунок 2.5 — График исследуемой функции

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.6

Рисунок 2.6 — График функции на выбранном отрезке

Проверяем существование корня на отрезке по условию

/>-3,066375

3,066375 <0, следовательно, на данном промежутке корень есть.

Исследуем функцию на монотонность:

6,2225>0

Экстремумов на выбранном отрезке нет.

Находим первую производную функции:

/>; />

В точке aпервая и вторая производные равны:

/>, />

В точке bпервая и вторая производные равны:

/>,/>

Выбираем тот конец отрезка, значение функции в котором совпадает со знаком 2-ой производной.

Принимаем:

x0= 1,5 />2.125*6.55=13,91875, />

По формуле

находим:

/>x>0.001

/>/>/>

/>x>0.001

/>x<0.001

Необходимая точность достигнута при n=4, т.е. на 4-й итерации.

Так как заданная точность достигнута, то процесс можно прекратить.

Теперь строим график функции x=/>, т.е. последовательность xn,стремящаяся к x*и условием сходимости здесь является /> (рисунок 2.7).

продолжение --PAGE_BREAK--

Рисунок 2.7 — График функции /> для исследуемой функции

2.3 Метод хорд

2.3.1 Общие сведения

Как и в методе хорд, функция f (x) должна удовлетворять на отрезке [a, b] следующим условиям:

1) существование производных 1-го и 2-го порядков;

2) f ’ (x) />0;

3) производные 1-го и 2-го порядков знакопостоянны на отрезке [a, b].

За начальное приближение x0 принимается один из концов отрезка [a, b], где значение функции имеет такой же знак, что и 2-я производная. За x1 выбирается второй край отрезка. В данном методе процесс итераций состоит в том, что в качестве приближений корню уравнения принимаются значения х0, х1,… точек пересечения хорды с осью абсцисс (рисунок 2.8).

Рисунок 2.8 — Метод хорд

Формула для n-го приближения имеет вид:

Итерационный процесс останавливают при выполнении условия />; где ε— заданная точность.

2.3.2 Решение нелинейного уравнения методом хорд

1. Дано уравнение

tg (0.36*x +0.4) =x2.

Решить его методом хорд с точностью решения/>=0,001.

Как в предыдущем методе для нахождения корня исследуем функцию

/>.

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.9

Рисунок 2.9 — График функции на выбранном отрезке

По данным из п.2.2.2 за x0выбираем тот конец отрезка, который совпадает со знаком 2-ой производной. А за x1 второй конец отрезка.

x0=-1; x1=0.

По формуле

находим:

/>x>0.001

/>x<0.001

Необходимая точность достигнута при n=7, т.е. на 6-й итерации.

Так как заданная точность достигнута, то процесс можно прекратить.

Теперь строим график функции x=/>, т.е. последовательность xn,стремящаяся к x*и условием сходимости здесь является /> (рисунок 2.10).

Рисунок 2.10 — График функции /> для исследуемой функции

2. Дано уравнение x3-0,2x2+0,4x-1,4=0. Решить его методом хорд с точностью решения/>=0,001.

Как в предыдущем методе для нахождения корня исследуем функцию

/>.

График функции представлен на рисунке 2.5

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.11

Рисунок 2.11 — График функции на выбранном отрезке.

По данным из п.2.2.2 за x0выбираем тот конец отрезка, который совпадает со знаком 2-ой производной и удовлетворяет условию />. А за x1 второй конец отрезка.

x0=1,5; x1=0,5.

По формуле

находим:

/>x>0.001

/>x<0.001

Необходимая точность достигнута при n=9, т.е. на 8-й итерации.

Так как заданная точность достигнута, то процесс можно прекратить.

Теперь строим график функции x=/>, т.е. последовательность xn,стремящаяся к x*и условием сходимости здесь является /> (рисунок 2.12).

Рисунок 2.12 — График функции /> для исследуемой функции.

2.4 Вывод

Судя по графикам и сравнивая эти два метода, можно сделать вывод, что искомый корень находится в промежутке между найденными приближенными корнями, т.е. для функции />на отрезке [-0.48059; — 0.48028], а для для функции />на отрезке [1,0627; 1,06289]

продолжение --PAGE_BREAK--

На рисунках 2.12, 2.13 приведены графики функций на данных отрезках.

Рисунок 2.12 — График функции />

Рисунок 2.13 — График функции />

Анализируя эти два метода, можно отметить, что в методе хорд, чтобы достичь заданной точности, необходимо выполнять больше итераций, чем в методе касательных. Так, в первом примере, в методе хорд мы выполнили 6 итераций, а в методе касательных всего 4; во втором примере в методе хорд мы выполнили 8 итераций, а в методе касательных всего 4. С другой стороны, в методе хорд не нужно вычислять производную функции на каждом шаге. Таким образом, как мне кажется, метод касательных является более трудоемким.

2.5 Метод простых итераций

2.5.1 Общие сведения

Пусть дано уравнение f (x) =0, (1)

Метод простых итераций уточнения корней уравнения (1) состоит в замене этого уравнения эквивалентным ему уравнением

/>(2)

и построении последовательности

/>(3),

где

/>,

Например

x= (а + b) /2

Если не удается выразить х из уравнения (1), то эквивалентное уравнение и эквивалентную функцию можно построить, например, так:

Последовательность (3) называют методом простых итераций уточнения корней уравнения (1).

Теорема (достаточное условие сходимости метода простых итераций). Пусть функция />в эквивалентном уравнении (2) определена и дифференцируема на отрезке /> Тогда, если существует число qтакое, что

но отрезке [а, b], то последовательность (3) сходится к единственному корню уравнения (2) при любом начальном приближении x.

Критерий окончания итерационного процесса. При заданной точности />>0 вычисления следует вести до тех пор, пока не окажется выполненным неравенство

Если величина />, то можно использовать более простой критерий окончания итераций:

2.5.2 Решение нелинейного уравнения методом простых итераций

1. Дано уравнение tg (0.36*x +0.4) =x2. Решить его методом простых итераций с точностью решения/>=0,001. Как в предыдущих методах для нахождения корня исследуем функцию

/>.

Выбираем концы отрезка: a= -1; b = 0. График функции на этом отрезке представлен на рисунке 2.14.

Рисунок 2.14 — График функции на выбранном отрезке

Приведем уравнение к виду x=x-f (x), где итерационная функция  (x) =x-f (x),  — итерационный параметр.

Максимальное и минимальное значения производной достигаются на концах отрезка:

/>/>

Применяем формулу x=x — f (x) = (x):

2. Дано уравнение x3-0,2x2+0,4x-1,4=0. Решить его методом методом простых итераций с точностью решения/>=0,001.

Для нахождения корня исследуем функцию />.

Выбираем концы отрезка: a= -0.1; b = 1.5 График функции на этом отрезке представлен на рисунке 2.15.

Рисунок 2.15 — График функции на выбранном отрезке.

Найдем корень с помощью встроенной функции root:

Приводим уравнение к виду x=(x), где

Проверим условие сходимости:

Максимальное по модулю значение производной итерационной функции достигается в левом конце отрезка:

Применяем формулу x=  (x):

2.6 Программа для решения нелинейных уравнений

На рисунках 2.16, 2.17 представлены программы для решения нелинейных уравнений методами хорд и касательных.

Пользователь вводит необходимые данные и при нажатии кнопки «Решить» выводится результат.

Листинги программ представлены в приложениях А, Б.

Рисунок 2.16 — Программа для решения методом касательных

Рисунок 2.17 — Программа для решения методом хорд

3. Решение нелинейных уравнений методом интерполирования

3.1 Интерполяция

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

Такая задача возникает по многим соображениям в частности, из-за удобства вычисления значений функции, вычисления производных и т.д.

Допустим, в n+1 точке заданы значения x0,x1,…xn и соответствующие им значения f (x0), f (x1), …, f (xn). Значения f (xi) вычисляются только в случае, если известна функция f (x), но эти значения могут быть получены, например, экспериментальным путем как значение некой неизвестной функции.

Точки xi, в которых известны значения функции, носят названия узлов интерполяции.

Интерполяция заключается в выборе функции φ (х), значения которой в узлах интерполяции совпадают со значениями f (xi).

φ (хi) = f (xi)

Между узлами значения этих функций могут отличаться (рисунок 3.1).

Рисунок 3.1 – Интерполяция

Мы рассмотрим простейший случай, когда в качестве интерполируемой функции используется полином степени n. Преимущества такой интерполяции очевидны. Значения полинома легко вычисляются, имеют непрерывную производную.

3.2 Многочлен Лагранжа

Пусть известны значения некоторой функции f в n+1 различных точках. Возникает задача приближенного восстановления функции f в произвольной точке x. Часто для решения этой задачи строится алгебраический многочлен Ln (x) степени n, который в точках xi принимает заданные значения, т.е.

Ln (xi) =fi, i=0,1,…,n

и называется интерполяционным.

В частности, мы рассматриваем построение интерполирующего многочлена Лагранжа.

/>,

где

fi — значения интерполируемой функции в i-том узле;

/> — коэффициент интерполяции Лагранжа

/>.

Можно сказать, что L1 (x) — линейная функция x, поэтому такую интерполяцию называют линейной (она производится для двух точек).

продолжение --PAGE_BREAK--

Интерполяционный многочлен Лагранжа обладает тем недостатком, что в случае, когда добавляются новые узлы интерполяции, все слагаемые необходимо пересчитывать. Но, с другой стороны, он обладает тем достоинством, что интервалы между узлами могут быть неравномерными.

Обратная интерполяция заключается в построении зависимости x (y) и, затем, с помощью такого многочлена легко можно найти корень нелинейного уравнения.

Многочлен Лагранжа в этом случае выглядит следующим образом:

/>,

где

xi — значения узлов;

/> — коэффициент интерполяции Лагранжа

/>.

Если задано достаточно много узлов на отрезке [a,b], то интерполирующие функции на отрезке [a,b] представляют собой непрерывную функцию, уже первая производная которой является кусочно-непрерывной.

В узлах, где происходит стыковка отдельных интерполяционных многочленов, производная рвется. Этого недостатка не имеет интерполяция сплайнами.

3.3 Интерполяция сплайнами

Пусть отрезок [a, b] разбит на n одинаковых частей точками x0, x1,…xn.

Примем

x=а, xn=b, h= (b-a) /n, xi= a+ih.

Сплайном называется непрерывная на [a, b] и имеющая непрерывные производные функция, на каждом из частичных участков представляющая собой алгебраический многочлен. Порядком сплайна называется старший порядок многочлена, а дефектом сплайна называется разность между порядком сплайна и старшей непрерывной производной.

Например, линейная интерполяция — это сплайн первого порядка с дефектом 1.

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

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

Этот сплайн не прерывен вместе с первой производной, но непрерывность второй производной не гарантируется, т.е. дефект сплайна равен 2. Если этот сплайн имеет непрерывную вторую производную на отрезке [a, b], т.е. имеет дефект 1, то такой сплайн носит название глобального.

Для построения кубического сплайна используется формула:

Для построения глобального сплайна, т.е. сплайна с дефектом 1 необходимо, начиная со 2-го узла, поставить условие непрерывности 2-й производной, т.е.2-я производная при подходе к точке 2 и дальше слева (x1-0) должна равняться второй производной при подходе справа (x1+0).

Такие равенства можно составить для всех внутренних узлов x1 до xn-1. Затем используем условия на краях x0и xn, получаем систему уравнений, которая и обеспечит дефект 1.

Очевидно, что при наличии S3 на соответствующих участках, построение таких равенств не представляет особого труда.

Приравнивая эти значения, для определения m получим СЛАУ.

/>/>

В двух крайних точках:

Если функция задана в виде таблиц, то для вычисления производных используеться результаты, получаемые при численном диференцировании, порядок точности которых не ниже 3-ей степени.

3.4 Использование интерполяции на практике

3.4.1 Интерполяция с помощью многочлена Лагранжа

Задание: найти приближенное значение функции при данном значении аргумента с помощью интерполяционного многочлена Лагранжа, если функция задана в неравносторонних узлах таблицы. Дана функция:

Составляем таблицу узлов интерполяции:

Поскольку n=5 строим интерполяционный многочлен L5 (x):

L5(x) =P50*f (x) +P51*f (x1) + P52*f (x2) + P53*f (x3) + P54*f (x4) + P55*f (x5) />

В результате получаем многочлен:

L5 (x) = 1.049*10-3*x5+5.4373*10-3*x4 +0.027*x3 — 0,936*x2 + 0,424*x +0.42278, X= — 0.48051

Подставляя заданное значение аргумента, получаем ответ:

L5 (x) = 0,00011

При подстановки того аргумента в заданную функцию, получаем такой же результат:

f (-0.48051) =0.00011

3.4.2 Обратная интерполяция

Задание: найти приближенное значение корня данном значении функции с помощью интерполяционного многочлена Лагранжа, если функция задана в равносторонних узлах таблицы.

Дана функция:

Составляем таблицу узлов интерполяции:

-0,7

-0.34091

-0,5

-0.02638

-0,3

0.21059

-0,1

0.37098

0,1

0.4559

Поскольку n=4 строим интерполяционный многочлен L4 (y):

L4(y) =P40*x+P41*x1+ P42*x2+ P43*x3+ P44*x4

В результате получаем многочлен:

L4 (y) = 7.99*y4-0.8176*y3 — 0.4932* y2 +0.9008*y — 0.4759

y= 0

Подставляя заданное значение функции, получаем ответ:

L4 (y) = — 0.47591

Таким образом, получаем приближенное значение корня:

продолжение --PAGE_BREAK--

X= — 0.47591

При подстановки этого аргумента в заданную функцию, получаем результат:

f (-0,47591) = 0.00625

3.4.3 Интерполяция сплайнами

Задание:

На участке [b,b+2] выбрать 3 точки (b,b+1,b+2), построить два сплайна на двух отрезках, убедиться в том, что в точке b+1 производная не терпит разрыва.

Построим таблицу:

0.42279

-0.4955

-1.93404

Для построения сплайна используем формулы:

h=/>

Таким образом, нам необходимо, чтобы вторая производная была непрерывна, т.е. получить сплайн с дефектом 1.

Для построения глобального сплайна необходимо, начиная со второго узла поставить условие непрерывности 2-ой производной, т.е.2-ая производная при подходе к точке 2 и дальше слева (x1-0) должна равняться 2-ой производной при подходе справа (x1+0):

Приравнивая эти значения, получаем:

Для нашей функции получаем:

/> 0.42435

/> — 2.10346

После того, как мы нашли m1, можем построить графики (рисунок 3.2).

/>/>/>/>/>

Рисунок 3.2 — Глобальная интерполяция сплайнами

Также можно сравнить с графиком самой функции (рисунок 3.3).

/>/>/>/>/>/>/>

Рисунок 3.3 — Сравнение графика функции и глобальной интерполяции

3.5 Программа для использования интерполяции

На рисунках 3.4 представлена программа для использования интерполяции сплайнами. Пользователь вводит необходимые данные и при нажатии кнопки «График» строится кубический сплайн.

Листинг программы представлен в приложении В.

Рисунок 3.4 — Программа для использования интерполяции сплайнами

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

4.1 Общие сведения

К численным методам линейной алгебры относятся численные методы решения систем линейных алгебраических уравнений. Методы решения СЛАУ разбиваются на две группы. К первой группе принадлежат так называемые точные или прямые методы — алгоритм, позволяющий получить решение системы за конечное число арифметических действий. Вторую группу составляют приближенные методы, в частности итерационные методы решения СЛАУ.

4.2 Метод простой итерации

4.2.1 Описание метода

Рассмотрим СЛАУ вида

Ax = B, где А — матрица. (1)

A = {aij}i, j = 1…n

B = {bi}x = {xi}

Если эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру

xk = Cxk-1 + D

xk → x*, где х* — решение заданной системы.

В конечном варианте система будет имееть вид:

x1=c11x1+c12x2+c13x3+…c1nxn+d1

x2=c21x1+c22x2+c23x3+…c2nxn+d1

x3=c31x1+c32x2+c33x3+…c1nxn+d3

…………………………………………. .

xn=cn1x1+cn2x2+cn3x3+…cnnxn+dn

Условием сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е.

/>, или />.

Необходимо, чтобы диагональные элементы матрицы А были ненулевыми.

Для преобразования системы можно выполнить следующие операции:

x1=a11-1(c1-a12x2— a13x3-… — a1nxn)

x2=a22-1 (c2-a21x2 — a23x3-… — a2nxn)

………………………. .

xn=ann-1 (cn-an1x2 — an3x3-… — an-1nxn-1)

В результате получим систему:

x1=0+ c12x2+ c13x3-…+ c1n-1xn-1+ c1nxn+d1

x2=c21x2+0 +c23x3+…+ c2n-1xn-1+ c2nxn+d2

………………………………………………………. .

xn=cn1x1+ cn2x2+cn3x3+…+ cnn-1xn-1+ 0+dn

продолжение --PAGE_BREAK--

В ней на главной диагонали матрицы С находятся нулевые элементы, остальные элементы выражаются по формулам:

сij=-aij/aii, di=ci/aii(i,j=1,2,3…n, i<>j)

Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k), х3(k) не станут близкими с заданной погрешностью к значениям х1(k-1), х2(k-1), х3(k-1).

4.2.2 Решение СЛАУ методом простых итераций

Решить СЛАУ методом простых итераций с точностью />.

Для удобства преобразуем систему к виду:

Условие сходимости:

/>,

Принимаем приближение на 0-ом шаге:

/>, />

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса:

/>:

На 2-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

/>: />

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

/>: />

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

/>: />

На 5-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

/>: />

На 6-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

/>: />

Необходимая точность достигнута на 6-й итерации. Таким образом, итерационный процесс можно прекратить.

4.2.3 Программа для решения СЛАУ методом простых итераций

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

Листинг программы приведен в приложении Г.

Рисунок 4.1 — Программа «Метод простых итераций»

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

4.3.1 Описание метода

В этом методе результаты, полученные на k-том шаге, используются на этом же шаге. На (k+1) — й итерации компоненты приближения /> вычисляются по формулам:

………………………………………….

Этот метод применим к система уравнений в виде Ax=B при условии, что диагональный элемент матрицы коэффициентов A по модулю должен быть больше, чем сумма модулей остальных элементов соответствующей строки (столбца).

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

/>, либо />

4.3.2 Решение СЛАУ методом Зейделя

Решить СЛАУ методом Зейделя с точностью />.

Эту систему можно записать в виде:

В этой системе сразу видно, что выполняется условие, где диагональные элементы матрицы коэффициентов по модулю больше, чем сумма модулей остальных элементов соответствующей строки.

Для удобства преобразуем систему к виду:

Условие сходимости:

/>,

Принимаем приближение на 0-ом шаге:

На 1-м шаге выполняем следующее:

Подставляем принятые приближения в первоначальную систему уравнений

Смотрим не выполняется ли условие остановки итерационного процесса

/>:

На 2-м шаге выполняем следующее:

продолжение --PAGE_BREAK--

Смотрим не выполняется ли условие остановки итерационного процесса

/>:

На 3-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса:

/>:

На 4-м шаге выполняем следующее:

Смотрим не выполняется ли условие остановки итерационного процесса

/>:

Необходимая точность достигнута на 4-й итерации. Таким образом, итерационный процесс можно прекратить.

4.3.3 Программа дл решения СЛАУ методом Зейделя

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

Листинг программы приведен в приложении Г.

Рисунок 4.2 — Программа «Метод Зейделя»

4.4 Сравнительный анализ

Можно заметить, что в методе Зейделя быстрее мы достигаемой нужной точности, в нашем случае в точность была достигнута на 4-й итерации, когда в методе простых итераций она была достигнута на 6-й итерации. Но в то же время в методе Зейделя ставится больше условий. Поэтому вначале нужно произвести иногда довольно трудоемкие преобразования. В таблице 4.1 приведены результаты решения СЛАУ методом простой итерации и методом Зейделя на различных шагах итерации:

Таблица 4.1 — Результаты решения СЛАУ

№ шага

Метод постой итерации

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

x1=1.34

x2=-1.75

x3=0.5

x4=0.65

x1=1.34

x2=-1.75

x3=0.5

x4=0.65

x1=1.277

x2=-1.56227

x3=0.3147

x4=0.5335

x1=1.277

x2=-1.57047

x3=0.3324

x4=0.5837

x1=1.31335

x2=-1.6127

x3=0.3647

x4=0.5884

x1=1.32469

x2=-1.5974

x3=0.355808

x4=0.58638

x1=1.315391

x2=-1.5935

x3=0.34936

x4=0.57867

x1=1.318014

x2=-1.5945

x3=0.354137

x4=0.58556

x1=1.3173416

x2=-1.5968

x3=0.35577

x4=0.58589

x1=1.318367

x2=-1.59481

x3=0.35437

x4=0.58554

x1=1.3179137

x2=-1.59467

x3=0.35371

x4=0.58462

x1=1.3181515

x2=-1.59506

x3=0.35455

x4=0.58557

5. Сравнительный анализ различных методов численного дифференцирования и интегрирования

5.1 Методы численного дифференцирования

5.1.1 Описание метода

Предположим, что в окрестности точки xiфункция F (x) дифференцируема достаточное число раз. Исходя из определения производной:

Для оценки погрешностей формул численного дифференцирования используется формула Тейлора:

/>(1)

Отбрасывая последнее слагаемое, мы можем вычислить производную.

Тогда отброшенное слагаемое будет являться погрешностью в формуле (1). В зависимости от того, какая точка выбирается за x отличают правостороннюю и левостороннюю производную.

Если для вычисления /> вместо x возьмем xi-1, то получится левосторонняя производная (2), а если xi+1, правосторонняя производная (1).

/> (1)

/> (2)

Отсюда видно, что порядок погрешности x — xi, т.е. при использовании

продолжение --PAGE_BREAK--

xi-1 или xi+1, порядка O (h).

При достаточно очевидном результате выражения (1) и (2) имеют низкую точность, т.е. высокую погрешность. Поэтому на практике больше используются так называемая центрально-симметричная формула, имеющая большой порядок точности.

Очевидно, что эта формула используется только для внутренних точек отрезка.

5.1.2 Нахождение производной

Вычислим производную функции f (x) =sin (x) в какой-либо точке на отрезке [0,π] двумя способами.

Разобьем отрезок на части:

h=/>

Найдем производную в точке x=/>.

По центрально-симметричной формуле:

По формуле правосторонней производной:

/>=cos (/>) =0.9659,

значит вычисление производной по центрально-симметричной формуле более точнее.

5.2 Методы численного интегрирования

5.2.1 Общие сведения

Для вычисления определённого интеграла используется формула:

Вычисление интеграла в таком виде не всегда удается, поэтому возникает задача приближенного значения этого интеграла.

В теории численного интегрирования используются следующие формулы для вычисления:

Формула левых прямоугольников:

Формула правых прямоугольников:

У этих формул погрешность порядка О (h).

Улучшения результатов можно добиться путем интерполирования (интерполирование можно вести на отрезке [a,b]). Интерполяция первого и второго порядка носит

Формула трапеции:

Формула Симпсона

/>, где n=2m

h=b-a/n

5.2.2 Нахождение определенного интеграла

Вычислим интеграл для функции /> разными способами.

Разобьем отрезок [0,/>] на части:

h=/>

По формуле левых прямоугольников:

По формуле трапеции:

По формуле Симпсона:

При m=3:

При m=2:

Сравним полученные результаты с табличным:

/>=1

Можно сделать вывод, при вычислении определенного интеграла наибольшую степень точности дает формула Симпсона.

5.3 Решение ОДУ

5.3.1 Решение ОДУ методом Эйлера

/>, />

Далее приведены результаты вычислений.

5.3.2 Решение ОДУ методом Рунге-Кутты

/>, />

Далее приведены результаты вычислений.

/>/>

Поправка Ричардсона Riдля метода Эйлера:

Поправка Ричардсона Riдля метода Рунге-Кутта:

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

6.1 Общие сведения

Обыкновенные дифференциальные уравнения являются моделью динамических систем. То есть систем меняющих свои свойства при изменении независимой переменной в качестве таковой очень часто выступает время.

Обыкновенными дифференциальными уравнениями называются такие уравнения, которые содержат одну или несколько производных от искомой функции y=y (x). Их можно записать в виде

/>,

где х — независимая переменная.

Наивысший порядок n входящей в уравнение

производной называется порядком дифференциального уравнения.

Методы решения обыкновенных дифференциальных уравнений можно разбить на следующие группы: графические, аналитические, приближенные и численные.

Графические методы используют геометрические построения.

Аналитические методы встречаются в курсе дифференциальных уравнений. Для уравнений первого порядка (с разделяющимися переменными, однородных, линейных и др.), а также для некоторых типов уравнений высших порядков (например, линейных с постоянными коэффициентами) удается получить решения в виде формул путем аналитических преобразований.

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

Численные методы решения дифференциальных уравнений в настоящее время являются основным инструментом при исследовании научно-технических задач, описываемых дифференциальными уравнениями. При этом необходимо подчеркнуть, что данные методы особенно эффективны в сочетании с использованием современных компьютеров.

Существуют различные задачи для ОДУ, мы будем рассматривать задачу Коши. Из курса математики известны условия существования единственности решения задачи Коши и также известно, что аналитически эта задача решается в достаточно редких случаях. То есть для того чтобы ОДУ являлась моделью некоторого динамического процесса, имела аналитическое решение приходится принимать слишком много предположений упрощающих исходную постановку. Что далеко не всегда является продуктивным.

6.2 Метод Эйлера

Начальные условия: х=х0, у=у0, />=f (x,y). Задача заключается в том, что необходимо построить функцию y=F (x) или Ф (х, у) =0, производная которой удовлетворяет заданному дифференциальному уравнению. Причем кривая соответствующей этой функции проходит через точку (х0, у0). Мы будем искать на заданном отрезке [a, b] х0=а значения некоторой функции, которые близки к соответствующим значениям искомого решения. Иногда говорят, что мы строим сеточную функцию, если разобьем отрезок [a, b] на n частей (h= (b-a) /n, где h — шаг сетки), тогда хi=x0+ih. Заменим в левой части производную /> правой разностью. При этом значения функции /> узлах /> заменим значениями сеточной функции />:

Полученная аппроксимация ДУ имеет первый порядок, поскольку при замене /> на

допускается погрешность />.

Будем считать для простоты узлы равноотстоящими, т.е.

Тогда из равенства

Получаем

Заметим, что из уравнения/> следует

/>.

Поэтому

представляет собой приближенное нахождение значение функции /> в точке /> при помощи разложения в ряд Тейлора с отбрасыванием членов второго и более высоких порядков. Другими словами, приращение функции полагается равным её дифференциалу. Полагая i=0, с помощью соотношения

находим значение сеточной функции /> при

/>: />.

Требуемое здесь значение /> задано начальным условием />, т.е. />. Аналогично могут быть найдены значения сеточной функции в других узлах:

Построенный алгоритм называется методом Эйлера, графически он представлен на рисунке 6.1.

Рисунок 6.1 -Метод Эйлера

5.3 Метод Рунге-Кутты

Одним из способов улучшения метода Эйлера является метод Рунге-Кутты. Формула Рунге — Кутты 4-го порядка:

/>, />

Заключение

В ходе выполнения курсовой работы был проведен сравнительный анализ численных методов, таких как итерация, интерполяция, численное дифференцирование и интегрирование, а также метод Эйлера.

В результаты все поставленные задачи были выполнены, цели достигнуты. Мы приобрели навыки в применении различных численных методов на практике. А также были исследованы различные методы.

Теперь перед нами стоит задача в применении приобретенных знаний в своей будущей профессиональной деятельности.

Список использованной литературы

Р.Ф. Хемминг «Численные методы (для научных работников и инженеров)». — Москва, 1972.

А.А. Амосов, А.Ю. Дубинский, Н.В. Копченова «Вычислительные методы для инженеров». — Москва, «Высшая школа», 1994.

Ф.В. Формалев, Д.Л. Ревизников «Численные методы». — М.: ФИЗМАТЛИТ, 2004.

Е.А. Волков. Численные методы: Учеб. Пособие для вузов — М.: Наука. Гл. ред. физ-мат. лит., 1987. — 248 с.

www.ronl.ru

Смотрите также

..:::Новинки:::..

Windows Commander 5.11 Свежая версия.

Новая версия
IrfanView 3.75 (рус)

Обновление текстового редактора TextEd, уже 1.75a

System mechanic 3.7f
Новая версия

Обновление плагинов для WC, смотрим :-)

Весь Winamp
Посетите новый сайт.

WinRaR 3.00
Релиз уже здесь

PowerDesk 4.0 free
Просто - напросто сильный upgrade проводника.

..:::Счетчики:::..