- •1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •2. Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •3. Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •5. Внутренняя сортировка данных методом «пузырька». Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •7. Численное решение уравнения методом половинного деления (дихотомии). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Метод хорд
- •9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •10. Численное решение уравнения модифицированным методом Ньютона. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Модифицированный метод Ньютона
- •Модифицированный метод Ньютона (метод секущих)
- •Метод ньютона-рафсона
- •11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Условие сходимости
- •12. Численное решение уравнения методом простых итераций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод простых итераций
- •13. Численное интегрирование методом прямоугольников. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод прямоугольников
- •Пример реализации
- •14. Численное интегрирование методом трапеций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод трапеций
- •Составная формула
- •Формула
- •Представление в виде метода Рунге-Кутта
- •Составная формула (формула Котеса)
- •16. Численное интегрирование методом Гаусса-Лежандра. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •17. Численное интегрирование методом Монте-Карло. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Интегрирование методом Монте-Карло
- •Обычный алгоритм Монте-Карло интегрирования
- •Геометрический алгоритм Монте-Карло интегрирования
- •Использование выборки по значимости
- •Применения
- •Случай равномерного распределения узлов интерполяции
- •Интерполяция полиномами Лагранжа и Ньютона
- •Погрешность интерполирования
- •Выбор узлов интерполяции
- •Изложение метода
- •Метод прогонки
- •Пример: интерполирование неизвестной функции
- •Ошибка интерполяции
- •Пример: интерполяция синуса
- •Дискретное преобразование Фурье
- •Пример использования
- •Погрешность вычислений
- •Программная реализация
Геометрический алгоритм Монте-Карло интегрирования
Рисунок 3. Численное интегрирование функции методом Монте-Карло
Для определения площади под графиком функции можно использовать следующий стохастический алгоритм:
ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого можно легко вычислить;
«набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек ( штук), координаты которых будем выбирать случайным образом;
определим число точек ( штук), которые попадут под график функции;
площадь области, ограниченной функцией и осями координат, даётся выражением
Для малого числа измерений интегрируемой функции производительность Монте-Карло интегрирования гораздо ниже, чем производительность детерминированных методов. Тем не менее, в некоторых случаях, когда функция задана неявно, а необходимо определить область, заданную в виде сложных неравенств, стохастический метод может оказаться более предпочтительным.
Использование выборки по значимости
При том же количестве случайных точек, точность вычислений можно увеличить, приблизив область, ограничивающую искомую функцию, к самой функции. Для этого необходимо использовать случайные величины с распределением, форма которого максимально близка к форме интегрируемой функции. На этом основан один из методов улучшения сходимости в вычислениях методом Монте-Карло: выборка по значимости.
Оптимизация
Применение в физике
Компьютерное моделирование играет в современной физике важную роль и метод Монте-Карло является одним из самых распространённых во многих областях от квантовой физики до физики твёрдого тела, физики плазмы и астрофизики.
18. Построение кривой по точкам. Интерполяционный полином Лагранжа. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для пар чисел , где все различны, существует единственный многочлен степени не более , для которого .
В простейшем случае () — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.
Определение
Этот пример показывает интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и(7,9), а также полиномы yi li(x), каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных xj
Лагранж предложил способ вычисления таких многочленов:
где базисные полиномы определяются по формуле:
обладают следующими свойствами:
являются многочленами степени
при
Отсюда следует, что , как линейная комбинация , может иметь степень не больше , и , Q.E.D.
Применения
Полиномы Лагранжа используются для интерполяции, а также для численного интегрирования.
Пусть для функции известны значения в некоторых точках. Тогда мы можем интерполировать эту функцию как
В частности,
Значения интегралов от не зависят от , и их можно вычислить заранее, зная последовательность .
Случай равномерного распределения узлов интерполяции
В случае равномерного распределения узлов интерполяции выражаются через расстояние между узлами интерполяции h и начальную точку :
,
и, следовательно,
Подставив эти выражения в формулу базисного полинома и вынеся h за знаки перемножения в числителе и знаменателе, получим
Теперь можно ввести замену переменной
и получить полином от , который строится с использованием только целочисленной арифметики. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования длинной арифметики.
19. Построение кривой по точкам. Интерполяционный полином Ньютона. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Многочлен Ньютона интерполяционный – как и другие интерполяционные формулы (см. интерполяция), служит для построения многочлена n-й степени, который совпадает в (n+1) точке co значениями неизвестной искомой функции у =f(x).
Пусть в точках х0, х1, …, хn+1 значения функции у = f(x) равны соответственноу0 = f(x0), y1 = f(x1), …, yn+1 = f(xn+1).
Построим интерполяционный многочлен Ньютона с помощью метода неопределенных коэффициентов. Для этого запишем искомый многочлен в виде Pn(x) = b0 + b1(x – x0) + b2(x – x0)(x – x1) + b3(x – x0)(x – x1)(x – x2) + … + bn(x – x0)…(x – xn). (1)
Последовательно подставляя в формулу (1) вместо х данные значения х0, х1, ...,хn+1, получим для нахождения неопределенных коэффициентов b0, b1, ..., bn«треугольную» систему уравнений (при подстановке в равенство (1) вместо х числа х0 в правой части равенства обратились в нуль все слагаемые, кроме первого: там везде был множитель (х – х0), обратившийся в нуль; при подстановке х = х1 обратились в нуль все слагаемые, кроме первого и второго – они содержат множитель (х – х1) и т.д.).
Полученную систему удобно решать: из первого её уравнения находим свободный член искомого многочлена b0; подставив его во второе уравнение, находим коэффициент b1 при первой степени х в искомом многочлене: и т.д.
Для интерполяционного многочлена Ньютона можно выписать явные выражения коэффициентов через данные задачи, а также и оценки точности замены неизвестной функции f(x) этим многочленом.