Лекция 1 Численные методы
Литература:
Предмет изучения численных методов
Методы решения математических задач:
Методы решения математических задач:
Методы решения математических задач:
Отличие вычислений «вручную» от компьютерных
Процесс решения задачи:
Решение нелинейных уравнений с одним неизвестным
Решить уравнение означает следующее:
Решение делится на 2 этапа:
Метод бисекции (деления отрезка пополам)
Метод бисекции
Метод бисекции
Графическое представление метода бисекции
Пример. Найти корень уравнения y = -x4 + 5 на интервале [0,∞] с точностью ε = 0.001
2. Решение методом бисекции в MathCAD
Решение нелинейных уравнений:
Метод хорд (пропорциональных частей)
Правила применения метода
I. Неподвижна точка B.
I. Неподвижна точка B.
Метод хорд (пропорциональных частей)
II. Неподвижна точка A.
II. Неподвижна точка A.
Вывод
Метод касательных (Ньютона)
Метод касательных (Ньютона)
Метод простой итерации
Метод простой итерации
Решение систем линейных алгебраических уравнений (СЛАУ)
Методы решения СЛАУ (самостоятельная работа)
3.48M
Категория: МатематикаМатематика

Численные методы

1. Лекция 1 Численные методы

1.
2.
Предмет изучения численных методов
Решение нелинейных уравнений
1

2. Литература:

Турчак Л.Е. Основы численных
методов. Учебное пособие. –
М.:Наука. – 2003. – 320 с.
Тарасевич. Основы численных
методов на MathCAD
www.exponenta.ru
Мудров А.Е. Числ. методы для ПЭВМ
на языках Бэйсик, Фортран и
Паскаль. – Томск:МП «Раско», 1991.
2

3. Предмет изучения численных методов

Область применения численных методов –
решение тех задач математического
анализа, для которых аналитическое
(точное) решение затруднено или
невозможно
Примеры:
«неберущиеся» интегралы (нет
первообразных функций);
Математические задачи, требующие
больших затрат времени
и другие
3

4. Методы решения математических задач:

Аналитические
Теоретические рассуждения и выводы.
Рассматриваются в курсе математики,
физики и др. наук.
Конечный результат: Формулы, системы
уравнений.
Преимущества:
1)
2)
3)
Вычисления по конечным формулам,
Можно строить графики
Решить доп. теоретические задачи
Недостатки:
1) Приближения при выводе формул
2) Отсутствие методов решения систем уравнений
некоторого вида
3) Трудности проведения вычислений по формулам4

5. Методы решения математических задач:

Графические
Построение графиков, диаграмм, запись
измерений с помощью датчиков.
Конечный результат: Графики и точки
на графиках.
Преимущества:
1)
2)
3)
Наглядное представление о поведении исследуемой величины
Позволяет оценить приближенное значение некоторой
величины
Можно составить таблицу значений
Недостатки:
1) Трудности проведения дополнительных
теоретических исследований
5

6. Методы решения математических задач:

Численные
Решение задачи сводится к вычислению в
определенной последовательности.
Конечный результат: Число или числа.
Преимущества:
1)
Решение задач, для которых нет аналитических
методов
Недостатки:
1) Вычисления содержат погрешности
2) Не для всех задач есть численные методы
3) Вычисления могут занимать много времени
6

7.

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

8. Отличие вычислений «вручную» от компьютерных

1. Вычисления с помощью ручки и бумаги
можно проводить с любой степенью точности
2. В компьютере числа хранятся в ячейках
памяти с фиксированной разрядностью не
более 15 цифр. Ограничен диапазон
представления чисел: 10-307 < |x| < 10307
3. Компьютерные вычисления могут содержать
миллионы операций, что приводит к
накоплению ошибки.
4. Компьютерная арифметика
связана с представлением чисел в
ЭВМ и отличается от обычной
8

9. Процесс решения задачи:

Постановка задачи (исходные данные и
определение конечного результата
исследования).
Построение модели (модель должна
адекватно описывать законы физического
явления).
Разработка численного метода (нахождение
метода, позволяющего свести задачу к
вычислительному алгоритму).
Все численные методы являются
ПРИБЛИЖЕННЫМИ, т.е. решение всегда
находится с некоторой погрешностью ε
9

10. Решение нелинейных уравнений с одним неизвестным

Опр. Нелинейным называется уравнение,
которое содержит неизвестное Xn (n≠1) или
переменная X входит под знак функции.
Опр. Если в уравнении переменная X входит
только в виде Xn (n≠1), то такое уравнение
называется алгебраическим.
Опр. Уравнение называется трансцендентным,
если переменная X входит под знак какой-либо
математической функции: корень, экспонента,
тригонометрическая функция и др.
10

11. Решить уравнение означает следующее:

1. Установить, имеет ли уравнение корни.
2. Определить число корней уравнения.
3. Найти значения корней уравнения с
заданной точностью.
11

12. Решение делится на 2 этапа:

1. Отделение корня X0 уравнения, т.е.
нахождение интервала (a,b), где X0∈(a,b), в
котором содержится корень уравнения.
а) Графически (строится приближенный
график функции y=f(x))
б) Аналитически (строится таблица
значений функции f(x)=0)
2. Уточнение значения корня X0 до
заданной точности ε.
12

13. Метод бисекции (деления отрезка пополам)

Постановка задачи: Решить уравнение f(x)=0.
Пусть на интервале [a,b] содержится один
корень уравнения x0. На данном интервале
выполняются ограничения применимости
метода:
1. f(a) · f(b) ≤ 0
2. Существует f’(x) и не меняет знак на [a,b]
3. Функция f(x) непрерывна и дифференцируема
на [a,b]
4. Задана точность нахождения корня X0: ε=10-3
13

14. Метод бисекции

Тогда, чтобы найти корень уравнения X0
необходимо сделать следующее:
1. Найти середину отрезка [a,b], точку c=(a+b)/2.
2. Найти значение функции f(x) в точке с.
3. Проверить, выполняется ли условие
f(с) · f(b) ≤ 0
(1).
4. В случае выполнения условия (1), сузить
интервал поиска до [c,b].
Если условие (1) не выполняется – сузить
интервал поиска до [a,c].
14

15. Метод бисекции

5. Переопределить интервал: новый
интервал поиска снова назвать как [a,b].
6. Проверить, достигнута ли заданная
точность ε:
| b – a| < ε
7. Если точность достигнута, то вывести на
печать значение корня X0 = (a+b)/2. Если
точность не достигнута, то перейти к п 1. (к
следующей итерации).
15

16. Графическое представление метода бисекции

x0
16

17. Пример. Найти корень уравнения y = -x4 + 5 на интервале [0,∞] с точностью ε = 0.001

1. Локализация (отделение) корня. Составим
таблицу значений функции f(x)=-x4+5:
x
F(x)
0
Y=5
1
Y=4
2
Y=-11
3
Y=-76
Из таблицы видно, что корень
находится на интервале x ∈ [1,2].
17

18. 2. Решение методом бисекции в MathCAD

1 итерация
a:= 1
b:= 2
c:=(a+b)/2 c=1.5
поэтому b:=c
f(b)*f(c) = 0.688 > 0
|b-a|=0.5 > ε
2 итерация
c:=(a+b)/2
c=1.25
поэтому a:=c
и т.д.
f(b)*f(c) = -0.16 < 0
|b-a|=0.25 > ε
18

19. Решение нелинейных уравнений:

1. Метод бисекции (деление отрезка
пополам);
2. Метод хорд (метод
пропорциональных частей);
3. Метод Ньютона (метод
касательных);
4. Метод итераций (метод
последовательных приближений).
19

20. Метод хорд (пропорциональных частей)

Постановка задачи та же, что и в методе
бисекций.
НЕПОДВИЖНА ТОЧКА B.
y
Проводим хорду AB,
которая делит отрезок
f(b)
[a,b] в соотношении:
-f(a) : f(b). Опускаем
перпендикуляр из т. x1
на функцию f(x).
Повторяем до тех пор,
пока не выполняется
o
условие
| xn+1 – xn| < ε .
f(a)
B
h1
x1
a
A
x2 x3
b
x0
x
C
20

21. Правила применения метода

1.
2.
Неподвижна та граница интервала, для
которой знак функции f(x) совпадает со
знаком ее второй производной f ”(x), т.е.
f(b)*f ”(b) >0.
Последовательные приближения xn лежат
по ту сторону корня x0, где функция имеет
знак, противоположный знаку ее второй
производной.
21

22. I. Неподвижна точка B.

Случай используется, если значение функции и
вторая производная функции f(x) в точке В имеют
одинаковые знаки, т.е.
f (b)*f “(b) > 0
Из подобия треугольников ΔAax1 и ΔABC
следует:
ax1
Aa
AC BC
h1
f (a)
b a f (a) f (b)
Тогда длина отрезка h1 равна:
f (a)
h1
(b a)
f (a) f (b)
22

23. I. Неподвижна точка B.

Найдем значение в т. x1:
f (a)
x1 a h1 a
(b a)
f (b) f (a)
Тогда последовательно находим
следующие точки:
f ( x1 )
x2 x1
f (b) f ( x1 )
f ( x2 )
x3 x2
(b x2 )
f (b) f ( x2 )
(b x1 )
и т.д.
Окончательно получаем:
f ( xn )
xn 1 xn
(b xn )
f (b) f ( xn )
(*)
23

24. Метод хорд (пропорциональных частей)

НЕПОДВИЖНА ТОЧКА А.
y
Проводим хорду AB,
которая делит отрезок f(a)
[a,b] в соотношении:
-f(b) : f(a). Опускаем
перпендикуляр из т. x1
на функцию f(x).
Повторяем до тех пор,
пока не выполняется
o
условие
| xn+1 – xn| < ε .
f(b)
A
x3
a
x0
x2 x1
h1
b
x
C
B
24

25. II. Неподвижна точка A.

Случай используется, если значение функции и
вторая производная функции f(x) имеют в точке А
одинаковые знаки, т.е.
f (a)*f “(a) < 0
Из подобия треугольников ΔBbx1 и ΔABC
следует:
bx1 bB
CB AC
h1
f (b)
b a f (a) f (b)
Тогда длина отрезка h1 равна:
f (b)
h1
(b a)
f (a) f (b)
25

26. II. Неподвижна точка A.

Найдем значение в т. x1:
f (b)
x1 b h1 b
(b a)
f (b) f (a)
Тогда последовательно находим
следующие точки:
f ( x1 )
x2 x1
f ( x1 ) f (a)
f ( x2 )
x3 x2
( x2 a )
f ( x2 ) f ( a )
( x1 a)
и т.д.
Окончательно получаем:
f ( xn )
xn 1 xn
( xn a )
f ( xn ) f ( a )
(**)
26

27. Вывод

Метод хорд заключается в том, что на
отрезке [a,b] функция f(x) заменяется
стягивающей её хордой.
В качестве приближенного значения корня
x0 принимается точка пересечения хорды с
осью Ox.
27

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

28

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

Известно начальное приближение для нахождения
корня x=c0 .
Тогда уравнение касательной, проведенной к кривой
y=F(x) в точке M0 с координатами (c0,F(c0)):
Отсюда следующее приближение корня с1 (точка
пересечения касательной с осью x):
Аналогично могут быть найдены следующие
приближения в точках М1,М2, … по формуле:
Необходимо, чтобы производная F’(ck-1)≠0
Условия окончания метода:
или
29

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

Пусть дано уравнение f(x)=0 (1) и на
интервале [a,b] существует единственный
корень уравнения x0. Найти корень с
точностью ε.
Приведем уравнение (1) к виду x=φ(x) (2),
где φ(x) – некоторая функция.
Выберем какое-либо приближенное
значение корня уравнения x1 и подставим
его в уравнение (2), получим x2= φ(x1).
Снова подставим x2 в правую часть
уравнения: x3= φ(x2) и т.д. Таким образом
получим последовательность: xn+1= φ(xn).
30

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

Для того чтобы метод сходился необходимо,
чтобы функция |φ’(x)|<1 на [a,b] .
Функция φ(x) выбирается в виде φ(x)=x+zf(x),
где z=const (z≠0).
Оценим значение z. Возможны 2 случая:
1) z=1/M, если M>1
2) z=1, если M<1.
M – максимальное значение производной
функции f’(x) на интервале [a,b]. Причем z
выбирают z<0, если f’(x) >0 и
z>0, если f’(x) <0.
Условие окончания метода: |xn+1 -xn|< ε.
31

32. Решение систем линейных алгебраических уравнений (СЛАУ)

В матричном виде система уравнений
записывается в виде:
n
aij x j bi , ( j 1,2,..., m)
i 1
Здесь aij – матрица коэффициентов при
неизвестных;
Bj – вектор-столбец свободных членов;
Xj – вектор-столбец неизвестных.
Решение: Любая совокупность
чисел α1, α2, …, αn, приводящая
систему в тождество

33. Методы решения СЛАУ (самостоятельная работа)

1. Метод Крамера (Правило Крамера)
2. Метод Гаусса (приведение расширенной
матрицы системы к треугольному виду):
а) неравенство нулю диагонального
элемента;
б) с выбором главного элемента;
в) итерационный.
3. Метод Жордана-Гаусса.
English     Русский Правила