ВМ (Ответы на экзаменационные вопросы в виде шпаргалки)

ВОПРОС №1. Основные понятия вычислительной математики. 1

ВОПРОС №2. Решение не линейного уравнения методом простейшей итерации. Понятие сжимающего отображения. Теорема о сходимости метода. Геометрическая интерпретация. 2

ВОПРОС №3. Уравнение МПИ. Условие на выбор числа r. Геометрическая интерпретация. 2

ВОПРОС №4. Метод Ньютона для решения не линейного уравнения. Условие сходимости метода. Геометрическая интерпретация. 3

ВОПРОС №5. Метод секущих. Условие сходимости. Геометрическая интерполяция. 3

ВОПРОС №6. Метод Стеффенсена. Условие сходимости. Геометрическая интерполяция. 3

ВОПРОС №7. Методы решения СЛАУ. Прямые и итерационные методы. Условие сходимости итерационных методов. 4

ВОПРОС №8. Метод простой итерации для решения СНУ. Теорема о сходимости методов. 5

ВОПРОС №9. Вопросы приближения функций. Постановка задачи. Понятие точной и интерполяционной аппроксимации. Интерпретационный многочлен Лагранжа. Теорема о единственности. 6

ВОПРОС №10. Вопросы приближения функций. Постановка задачи. Многочлен Ньютона с распределяющими разностями. 7

ВОПРОС №11. Вопросы приближения функций. Постановка задачи. Многочлен Ньютона с конечными разностями для интерполяции вперёд. 7

ВОПРОС №12. Многочлен Ньютона с конечными разностями для интерполяции назад. 8

ВОПРОС №13. Многочлен Ньютона с конечными разностями для интерполяции Сплайны. 9

ВОПРОС №14. Многочлен Ньютона с оконченными разностями для интерполяции. Характер экспериментальных данных. Понятие аппроксимации. Метод выбранных точек и средних. 10

ВОПРОС №15. Метод наименьших квадратов. 11

ВОПРОС №17. Численное интегрирование и дифференцирование. 11

ВОПРОС №18. Общая постановка задачи Коши. Метод Эйлера для её решения. 12

ВОПРОС №19. Общая постановка задачи Коши. Метод Рунге – Кутта для её решения. Метод Рунге – Кутта 4-го порядка точности. 13

ВОПРОС 20. Постановка 2-х точной краевой задачи. Её 14

ВОПРОС №21. Вычисление собственных чисел матрицы. 14

ВОПРОС №1. Основные понятия вычислительной математики.

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

Всякая математическая модель представляет собой математическое преобразование вида

Y=F(x,u)

где x = (x1,...,xn) - совокупность входных параметров;

y = (y1,...,yn) - совокупность выходных параметров объекта;

U = (U1,...,Un) - совокупность входных управляющих воздействий, с помощью которых осуществляется управление процессами;

F - оператор преобразования.

Для решения математических задач в САПР применяются три группы методов: графические, аналитические, численные.

Графические методы предполагают искать решение с помощью геометрических построений.

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

Численные методы являются основными методами в САПР. В их основе лежит процедура сведения решения задачи к конечному числу арифметических действий над числами, и получить результат в виде численных значений.

Основные требования и показатели численных методов:

1) устойчивость;

2) сходимость;

3) эффективность (скорость сходимости);

4) погрешность.

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

Сходимость является основным критерием оценки алгоритма. Алгоритм сходится, если итерационная последовательность приближений.

x¹,x²,...,x^k x^* , k   , т. е.

Скорость сходимости. (эффективность) – обозначает количество итераций, затраченных алгоритмом для достижения приемлемой точности решения задачи. Сущ. 3 оценки скорости сходимости: линейная и сверх линейная. Пусть x^kx^* , k  

Говорят, что алгоритм обладает линейной скоростью сходимости, если g э [0;1] и R0

|x^k+1-x^*|g_k |x^k-x^*| , при kk₀

Алгоритм обладает сверх линейной скоростью сходимости, если выполняется условие

|x^k+1-x^*|g_k |x^k-x^*| , g 0 , k  

Алгоритм обладает квадратичной скоростью сходимости, если

|x^k+1-x^*|c |x^k-x^*| , c 0

ВОПРОС №2. Решение не линейного уравнения методом простейшей итерации. Понятие сжимающего отображения. Теорема о сходимости метода. Геометрическая интерпретация.

Алгоритмы решения нелинейного уравнения. Метод итераций.

Пусть требуется решить уравнения вида f(x)=0 (*), где f(x) - непрерывная функция.

Чтобы методом итераций найти решение уравнения (*) его необходимо преобразовать к виду

x⁽¹⁾ = (x⁽⁰⁾) (**)

Зададим начальное приближение x₀ и подставим его в правую часть уравнения (**).

Получим значение х₁

Подставив значение х₁ в правую часть уравнения (**) получим х₂

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

x^k+1=(x^k) , k 0 (***)

Условие сходимости метода. Теорема. Пусть в некоторой  - окрестности корня х^* функция (x) непрерывна и дифференцируема и удовлетворяет неравенству | ' (x)| g, (5) где 0 < g < 1 - константа. Тогда независимо от выбора начального приближения х⁽⁰⁾ из указанной  - окрестности корня итерационная последовательность не выходит из этой окрестности и справедлива следующая оценка погрешности: Неравенство (5) означает, что метод простой итерации обладает линейной скоростью сходимости.

Геометрическая интерпретация метода. На рис.1 (а) видно, что корень уравнения (1) является абсциссой точки пересечения графиков двух функций y = x и y =  (x). В случаях (а) и (б) метод простой итерации сходится при произвольном начальном приближении. В случаях (в) и (г) метод расходится при любом начальном приближении. Замечено, что в случаях (а) и (б)    (x)  < 1, а в случаях (в) и (г)    (x)  > 1.

Сжимающее отображение. Понятие с.о. позволяет решать вопрос о сходимости итерационного процесса аналитически, а не геометрическими построениями. Возьмем непрерывную  (x), заданную на отрезке  a; b . Каждой т. x   a; b соответствует y =  (x ) на оси ординат.

Т.е. функция  (x) задает отображение отрезка  a; b на оси ординат. Чтобы сравнить образ отрезка с самим отрезком необходимо отобразить точки на оси 0y через прямую y = x на ось 0x. Если образ отрезка  a; b  является частью  a; b , то  (x) отображает  a; b в себя. Построим последовательность  a; b ;  a ; b  ;  a ; b  и т.д. Если после каждого отображения отрезок уменьшается в М>1 раз, то отображение называется сжимающим.

Расстояние между двумя т. x1 и x2 =  x2 - x1  . Условие сжатия формулируется: отображение  (x) является сжимающим на отрезке  a; b , если существует 0<x<1 и для любых двух точек x1 , x2   a; b выполняется неравенство:

  (x2 ) -  (x1 )    x2 - x1  ,  = 1/М.

ВОПРОС №3. Уравнение МПИ. Условие на выбор числа r. Геометрическая интерпретация.

Модификация итерационного процесса.

Применение метода итераций x =(x); часто затрудняется тем, что  (x) несжимающая функция. Помимо этого можно потребовать увеличение скорости сходимости.

Рассмотрим исходное уравнение

f (x) = 0, (1) где f (x) =  (x) – x. Решение x итерационного процесса будет и решением (1).

Преобразуем (1) следующим образом f (x) = 0  r f (x) = 0  x = x + r f (x) или x =  (x) (2)

где f (x) = x + r f (x), r  0.

Итерационный процесс происходит по формуле

x =  (x ) или x = x + r f (x ),  = 0,1,2, ... (3)

Решение (2) является решением (1).

В предложенном варианте существование решения и сходимость x , x , x , ... , x , ... обеспечивается условиями теоремы сжатия относительно  (x). При этом r может быть выбрана таким методом, что условие сжатия выполняется для  (x) в тех случаях, когда  (x) несжимаема.

Пусть    (x)  >1 для итерационного процесса x =  (x). Будем искать решение (1) решая (2) с помощью алгоритма (3), а число r выберем из условия сжатия для  (x) при x = x*.

   (x*) < 1, или  1+ r f  (x*) < 1,  1+ r(  (x*) – 1)  < 1 (4)

-1<1+ r(  (x*) – 1) < 1 

 -2< r(  (x*) – 1) < 0

 -2/  (x*) – 1< r< 0,

r< 0 и  r < 2 /  (x*) – 1, если   - 1> 0

r> 0 и  r < 2 /  (x) – 1, если   - 1> 0

Из условия сжатия функции  (x) получим рекомендации для выбора числа r в уравнении (2) и алгоритма (3), обеспечивающих сходимость (3). Можно потребовать наиболее сильного сжатия,   (x*) = 0 (5) Отсюда получаем значение r = -1/   (x*) – 1 (6)

Геометрическая интерпретация.

Касательная в т. Bn y – f(x ) = f (x )(x-xn ).

ВОПРОС №4. Метод Ньютона для решения не линейного уравнения. Условие сходимости метода. Геометрическая интерпретация.

Метод Ньютона. В предложенной методике есть недостаток: r = const на протяжении всего процесса поиска корня. Однако нет препятствий для изменения этого значения в процессе выполнения итерационного процесса. Сделаем r функцией x и подставим в алгоритм:

x = x + r(x ) f (x ), n = 0,1,2, ... .(7)

Потребуем, чтобы   (x) была = 0 в достаточно большой окрестности корня x*:

  (x) = 1 + r f  (x) = 0,

отсюда r(x) = -1/ f  (x) = -1/  (x) –1.

Тогда алгоритм будет иметь вид:

x(n+1) = x^(к) - f(x^(к)) / f  (x^(к)) – метод Ньютона.

Условие сходимости метода. Для вывода сходимости метода потребуем сжатия функции (x)=x-f(x) / f ‘(x) на произвольном отрезке: x ∊ [a;b]. Если ф-я f(x) – сжимающая, то для люб. x₀, x₁ из отрезка [a;b] должно происходить уменьшение длины (x₁ – x₀) при каждом новом отображении ф-и (x). Запишем условие сжатия след. образом:

В ф-ле сжимающегося отобр-я x<1 отсюда если вып. M/m*|x₁-x₀|<1, то метод сходится. |x^k+1-x^*|  M / m |x^k-x^*|²

Геометрическая интерпретация.

Касательная в т. Bn y – f(x ) = f (x )(x-xn ).

ВОПРОС №5. Метод секущих. Условие сходимости. Геометрическая интерполяция.

М етод секущих. Полагая y = 0, x = xn+1 получим формулу для метода Ньютона. Если значения производной вычислять приближенно, как приращение f(x) в т. x и xn-1, то получим метод секущих.

При условии x = x и y(x) = 0 получим (1).

Оценка скорости сходимости (***).

Условие сходимости метода. Для вывода сходимости метода потребуем сжатия функции (x)=x-f(x) / f ‘(x) на произвольном отрезке: x ∊ [a;b]. Если ф-я f(x) – сжимающая, то для люб. x₀, x₁ из отрезка [a;b] должно происходить уменьшение длины (x₁ – x₀) при каждом новом отображении ф-и (x). Запишем условие сжатия след. образом:

В ф-ле сжимающегося отобр-я x<1 отсюда если вып. M/m*|x₁-x₀|<1, то метод сходится. |x^k+1-x^*|  M / m |x^k-x^*|²

ВОПРОС №6. Метод Стеффенсена. Условие сходимости. Геометрическая интерполяция.