2014 г
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Обзор численных методов презентация
Содержание
- 1. Обзор численных методов
- 2. Литература В. М. Вержбицкий, Основы численных методов,
- 3. Решение нелинейных алгебраических уравнений Пусть функция f(x)
- 4. Решение нелинейных алгебраических уравнений. Алгоритм метода половинного
- 5. Блок-схема метода половинного деления
- 6. Решение нелинейных алгебраических уравнений. Алгоритм метода секущих
- 7. Решение нелинейных алгебраических уравнений. Алгоритм метода Стеффенсена
- 8. Решение нелинейных алгебраических уравнений. Алгоритм метода простой
- 9. Трёхдиагональная СЛАУ Трёхдиагональными называются матрицы, каждая строка
- 10. Системы линейных алгебраических уравнений (СЛАУ) СЛАУ в
- 11. Решение трёхдиагональной СЛАУ методом прогонки Прямой ход
- 12. Решение СЛАУ методом Гаусса Прямой ход метода
- 13. Алгоритм решения СЛАУ методом Гаусса В. М. Вержбицкий, Основы численных методов, Высшая школа, 2005 г
- 14. LU-разложение Любая матрица А(n x n) может
- 15. LU-разложение (продолжение) Из оставшейся части 2-й строки
- 16. Решение СЛАУ при помощи LU-разложения Система Ax=b
- 17. Решение СЛАУ методом простых итераций Сначала надо
- 18. Решение СЛАУ методом Зейделя Вариант метода простых
- 19. Одномерная оптимизация. Метод деления отрезка пополам
- 20. Одномерная оптимизация. Метод деления отрезка пополам А.
- 21. Одномерная оптимизация. Метод золотого сечения А. В.
- 22. Одномерная оптимизация. Метод Фибоначчи
- 23. Одномерная оптимизация. Метод Фибоначчи (продолжение) А. В.
- 24. Одномерная оптимизация. Метод квадратичной интерполяции А. В.
- 25. Одномерная оптимизация. Метод квадратичной интерполяции (продолжение)
- 26. Интерполяционный полином Лагранжа В. М. Вержбицкий, Основы
- 27. Линейная задача наименьших квадратов (МНК) Функция y=f(x)
- 28. Метод МНК (продолжение) Из различных критериев выбора
- 29. Метод МНК (продолжение) Опуская промежуточные выкладки, для
- 30. Метод МНК (продолжение) Для m=1, P1=a0+a1x Нормальная
- 31. Интегрирование. Формулы прямоугольников, трапеций и Симпсона
- 32. Квадратурные формулы Квадратурные формулы: Хi – узлы;
- 33. Квадратурные формулы (продолжение) Целесообразно отказаться от равноотстоящих
- 34. Квадратурная формула Чебышева При Аi ≡ A
- 35. Квадратурная формула Гаусса При неравенстве Аi друг
- 36. Узлы и веса для квадратур Чебышева и Гаусса
- 37. Решение задачи Коши для обыкновенных дифференциальных уравнений
- 38. СПАСИБО ЗА ВНИМАНИЕ!
Литература В. М. Вержбицкий, Основы численных методов, Высшая школа, 2005 г. А.А. Амосов, Ю.А. Дубинский, Н.В. Копченова, Вычислительные методы для инженеров, Высшая школа, 1994 А. В. Пантелеев, Т. А. Летова Методы
Слайд 1Обзор численных методов
Лекция 5.
РХТУ им. Д.И. Менделеева
Каф. ИКТ
Курс создал:
ст. преп. A.М. Васецкий
Слайд 2Литература
В. М. Вержбицкий, Основы численных методов, Высшая школа, 2005 г.
А.А. Амосов,
Ю.А. Дубинский, Н.В. Копченова, Вычислительные методы для инженеров, Высшая школа, 1994
А. В. Пантелеев, Т. А. Летова Методы оптимизации в примерах и задачах. Прикладная математика для ВТУЗов, Высшая школа, 2008
А. В. Пантелеев, Т. А. Летова Методы оптимизации в примерах и задачах. Прикладная математика для ВТУЗов, Высшая школа, 2008
Слайд 3Решение нелинейных алгебраических уравнений
Пусть функция f(x) определена и непрерывна при всех
х на отрезке [а,b] и на [а,b] меняет знак, т.е. f(a)*f(b)<0.
Тогда уравнение f(x)=0 имеет на (а, b) хотя бы один корень.
Тогда уравнение f(x)=0 имеет на (а, b) хотя бы один корень.
Слайд 4Решение нелинейных алгебраических уравнений. Алгоритм метода половинного деления
В. М. Вержбицкий, Основы
численных методов, Высшая школа, 2005 г.
Слайд 6Решение нелинейных алгебраических уравнений. Алгоритм метода секущих
В. М. Вержбицкий, Основы численных
методов, Высшая школа, 2005 г.
Х0 и Х1 – начальные точки. Задаются пользователем.
Метод не сходится при Хk=Xk-1
Примечание: Решение уравнений, где Х – кратный 0 (f’(x)=0) представляет для метода определённые трудности.
Слайд 7Решение нелинейных алгебраических уравнений. Алгоритм метода Стеффенсена
В. М. Вержбицкий, Основы численных
методов, Высшая школа, 2005 г, с.221
Х0– начальная точка.
Метод не сходится при Хk=Xk-1
Решение уравнений, где Х – кратный 0 (f’(x)=0) представляет для метода определённые трудности.
Локально имеет квадратичную сходимость
Слайд 8Решение нелинейных алгебраических уравнений. Алгоритм метода простой итерации
Чтобы применить метод простой
итерации необходимо преобразовать исходное уравнение к виду х=ϕ(x).
Далее выбирается начальное приближение корня х0 и вычисления проводят по схеме xn+1= ϕ(xn).
Сходимость обеспечивается при |ϕ’(xn)|
Далее выбирается начальное приближение корня х0 и вычисления проводят по схеме xn+1= ϕ(xn).
Сходимость обеспечивается при |ϕ’(xn)|
Слайд 9Трёхдиагональная СЛАУ
Трёхдиагональными называются матрицы, каждая строка которых содержит 3 соседних неизвестных:
bixi-1+cixi+dixi+1=ri,
b1=0, dn=0, i=1..n
Или в матричной форме:
Или в матричной форме:
Слайд 10Системы линейных алгебраических уравнений (СЛАУ)
СЛАУ в матричном виде записывается как А*x=b,
где
В Excel удобно решать СЛАУ с использованием функций листа Excel и формулы:
x=A-1b
Слайд 11Решение трёхдиагональной СЛАУ методом прогонки
Прямой ход метода прогонки:
Определение коэффициентов δi, λi,
i=2..n
δ1=-d1/c1; λ1=r1/c1
Обратный ход метода прогонки:
xn=λn
xi=δixi+1+λi i=n-1,..1
Задача корректна (ci+bidi-1≠0) и устойчива (|δi|<1) при
|ci|>|bi|+|di|
δ1=-d1/c1; λ1=r1/c1
Обратный ход метода прогонки:
xn=λn
xi=δixi+1+λi i=n-1,..1
Задача корректна (ci+bidi-1≠0) и устойчива (|δi|<1) при
|ci|>|bi|+|di|
В. М. Вержбицкий, Основы численных методов, Высшая школа, 2005 г, с.75
Слайд 12Решение СЛАУ методом Гаусса
Прямой ход метода Гаусса
(приведение к треугольному виду)
Обратный
ход метода Гаусса
(получение значений неизвестных)
(получение значений неизвестных)
Слайд 13Алгоритм решения СЛАУ методом Гаусса
В. М. Вержбицкий, Основы численных методов, Высшая
школа, 2005 г
Слайд 14LU-разложение
Любая матрица А(n x n) может быть преобразована представлена как произведение
нижней (L) и верхней (U) треугольных матриц следующим образом:
Элементы uij и lij находятся поочерёдно.
Из 1-й строки: u1j=a1j (j=1…n)
Из оставшейся части 1-го столбца:
li1=ai1/u11 (i=2…n)
Слайд 15LU-разложение (продолжение)
Из оставшейся части 2-й строки
u2j=a2j-l21u1j (j=2,...,n)
Из оставшейся части 2-го столбца
li2=(ai2-li1u12)/u22
(i=3,…,n)
…
Т.е. все отличные от 0 и 1 элементы матриц L и U могут быть вычислены при помощи формул:
…
Т.е. все отличные от 0 и 1 элементы матриц L и U могут быть вычислены при помощи формул:
Слайд 16Решение СЛАУ при помощи LU-разложения
Система Ax=b преобразуется к LUx=b
Или, вводя вектор
вспомогательных переменных y: Ly=b и Ux=y
i=1..n
i=n..1
Слайд 17Решение СЛАУ методом простых итераций
Сначала надо привести функцию, удобному для метода
итераций: x=ϕ(x).
Итерационная процедура представлена в виде:
Итерационная процедура представлена в виде:
Сходимость метода обеспечивается в случае, когда норма матрицы Якоби меньше либо равна константе q: || ϕ ‘||≤q<1
А.А. Амосов, Ю.А. Дубинский, Н.В. Копченова, Вычислительные методы для инженеров, Высшая школа, 1994
Слайд 18Решение СЛАУ методом Зейделя
Вариант метода простых итераций, где часть переменных хk
заменена на xk+1
В. М. Вержбицкий, Основы численных методов, Высшая школа, 2005 г
Слайд 20Одномерная оптимизация.
Метод деления отрезка пополам
А. В. Пантелеев, Т. А. Летова. Методы
оптимизации в примерах и задачах. Прикладная математика для ВТУЗов, Высшая школа, 2008
Слайд 21Одномерная оптимизация.
Метод золотого сечения
А. В. Пантелеев, Т. А. Летова Методы оптимизации
в примерах и задачах. Прикладная математика для ВТУЗов, Высшая школа, 2008
Слайд 23Одномерная оптимизация.
Метод Фибоначчи (продолжение)
А. В. Пантелеев, Т. А. Летова Методы оптимизации
в примерах и задачах. Прикладная математика для ВТУЗов, Высшая школа, 2008
Слайд 24Одномерная оптимизация.
Метод квадратичной интерполяции
А. В. Пантелеев, Т. А. Летова Методы оптимизации
в примерах и задачах. Прикладная математика для ВТУЗов, Высшая школа, 2008
Слайд 26Интерполяционный полином Лагранжа
В. М. Вержбицкий, Основы численных методов, Высшая школа, 2005
г.
Для заданной таблично функции yi≈f(xi), i=0..n требуется интерполировать функцию между узлами интерполяции с использованием полинома Лагранжа
Слайд 27Линейная задача наименьших квадратов (МНК)
Функция y=f(x) задана таблицей приближенных значений yi≈f(xi),
i=0..n
Для аппроксимации используется линейная модель:
y=Φm(x)=a0ϕ0(x)+a1 ϕ 1(x)+…+amϕ m(x)
Где ϕ i(x) – базисные функции,
аi – параметры модели.
Для полиномиальной модели ϕk=xk:
y=Pm(x)=a0+a1x+…+amxm
При m=n многочлен МНК совпадает с интерполяционным многочленом.
Как правило, при использовании метода МНК m≤n.
Для аппроксимации используется линейная модель:
y=Φm(x)=a0ϕ0(x)+a1 ϕ 1(x)+…+amϕ m(x)
Где ϕ i(x) – базисные функции,
аi – параметры модели.
Для полиномиальной модели ϕk=xk:
y=Pm(x)=a0+a1x+…+amxm
При m=n многочлен МНК совпадает с интерполяционным многочленом.
Как правило, при использовании метода МНК m≤n.
Слайд 28Метод МНК (продолжение)
Из различных критериев выбора параметров ai наиболее часто используется
критерий наименьших квадратов. Согласно ему минимизируется среднеквадратичное отклонение:
В точках xi выполняются приближённые равенства:
Или в матричном виде: Pa≈y
Слайд 29Метод МНК (продолжение)
Опуская промежуточные выкладки, для получения параметров ai требуется решить
СЛАУ:
Или для случая полиномиальной модели:
А.А. Амосов, Ю.А. Дубинский, Н.В. Копченова, Вычислительные методы для инженеров, Высшая школа, 1994
Слайд 30Метод МНК (продолжение)
Для m=1, P1=a0+a1x
Нормальная система имеет вид:
Для m=2, P1=a0+a1x+a2x2
Нормальная система
имеет вид:
Слайд 31Интегрирование.
Формулы прямоугольников, трапеций и Симпсона
Квадратурные формулы левых и правых прямоугольников
Формула
трапеций
Формула Симпсона (парабол)
Формула Симпсона (парабол)
Слайд 32Квадратурные формулы
Квадратурные формулы:
Хi – узлы;
Аi – веса;
В ранее рассмотренных формулах узлы
равноотстоящие и наборы весов следующие:
Для формулы трапеций:
h/2, h,...,h, h/2
Для формулы Симпсона:
h/3,4h/3,2h/3,4h/3,...,4h/3,h/3
Для формулы трапеций:
h/2, h,...,h, h/2
Для формулы Симпсона:
h/3,4h/3,2h/3,4h/3,...,4h/3,h/3
Слайд 33Квадратурные формулы (продолжение)
Целесообразно отказаться от равноотстоящих узлов и преобразовать:
Целесообразно отказаться от
равноотстоящих узлов и преобразовать:
Интеграл преобразуется к виду:
Переходя к квадратурной формуле:
Слайд 34Квадратурная формула Чебышева
При Аi ≡ A = 2/n и таких ti,
что формула точна для многочленов степени n на отрезке [-1;1], она преобразуется к виду:
Расположение узлов ti вычисляется из решения системы нелинейных уравнений (здесь не приводится). Такие наборы ti существуют для i=1,2,..7,9 и приводятся ниже
Слайд 35Квадратурная формула Гаусса
При неравенстве Аi друг другу квадратурная формула имеет более
общий вид.
Узлами её являются корни многочлена Лежандра, χn(t), а веса находятся интегрированием базисных многочленов Лежандра.
Общая формула для квадратур Чебышева и Гаусса на интервале [a,b]
Узлами её являются корни многочлена Лежандра, χn(t), а веса находятся интегрированием базисных многочленов Лежандра.
Общая формула для квадратур Чебышева и Гаусса на интервале [a,b]
Слайд 37Решение задачи Коши для обыкновенных дифференциальных уравнений
ОДУ 1-го порядка: y’=f(x,y), x∈[x0,b]
Начальное
условие – y(x0)=y0
Метод Эйлера: yi+1=yi+h*f(xi,yi), i=0..n
Метод Эйлера-Коши (Хьюна):
yi+1=yi+h/2*(f(xi,yi)+f(xi+1,yi+hf(xi,yi))), i=0..n
Метод Рунге-Кутта 4-го порядка:
Метод Эйлера: yi+1=yi+h*f(xi,yi), i=0..n
Метод Эйлера-Коши (Хьюна):
yi+1=yi+h/2*(f(xi,yi)+f(xi+1,yi+hf(xi,yi))), i=0..n
Метод Рунге-Кутта 4-го порядка:
А.А. Амосов, Ю.А. Дубинский, Н.В. Копченова, Вычислительные методы для инженеров, Высшая школа, 1994
