Участник:Valkyrie - История изменений

Valkyrie: Полностью удалено содержимое страницы

2017-10-22T20:04:14Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 20:04, 22 октября 2017
Строка 1:		Строка 1:
	~~{{algorithm~~
	~~\| name = Адаптивное интегрирование~~
	~~\| serial_complexity =~~
	~~\| input_data =~~
	~~\| output_data =~~
	}}

	~~Автор: [[Участник:Valkyrie\|В.А. Мастинен]]~~

	~~== Свойства и структура алгоритма ==~~

	~~=== Общее описание алгоритма ===~~

	Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

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

	На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

	~~=== Математическое описание алгоритма ===~~

	Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>

	~~Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>~~

	~~Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>~~

	~~Оценим <math>\tau \approx \|Q(a,b) - \int\limits_a^b f(x)\,dx\|</math>~~

	Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,\frac{a+b}2]</math> и <math>[\frac{a+b}2,b]</math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>

	Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{\|Q(a,c) + Q(c,b) - Q(a,b)\|}{15}</math><ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>

	~~=== Вычислительное ядро алгоритма ===~~

	~~=== Макроструктура алгоритма ===~~

	~~=== Последовательная сложность алгоритма ===~~

	~~=== Информационный граф ===~~

	~~=== Ресурс параллелизма алгоритма ===~~

	~~=== Входные и выходные данные алгоритма ===~~

	~~=== Свойства алгоритма ===~~

	~~== Программная реализация алгоритма ==~~

	~~=== Особенности реализации последовательного алгоритма ===~~

	~~=== Локальность данных и вычислений ===~~

	~~=== Возможные способы и особенности параллельной реализации алгоритма ===~~

	~~=== Масштабируемость алгоритма и его реализации ===~~

	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~

	~~=== Выводы для классов архитектур ===~~

	~~=== Существующие реализации алгоритма ===~~

	~~== Литература ==~~

Valkyrie: /* Общее описание алгоритма */

2017-10-22T20:01:58Z

Общее описание алгоритма

← Предыдущая версия		Версия от 20:01, 22 октября 2017
Строка 12:		Строка 12:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для ~~«хороших»~~ подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.		Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

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

Valkyrie: /* Общее описание алгоритма */

2017-10-22T20:00:37Z

Общее описание алгоритма

← Предыдущая версия		Версия от 20:00, 22 октября 2017
Строка 12:		Строка 12:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических ~~квадратурных формул~~[http://algowiki-project.org/ru/Квадратурные_формулы]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «хороших» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.		Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «хороших» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

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

Valkyrie: Новая страница: «{{algorithm | name = Адаптивное интегрирование | serial_complexity = | input_data = | output_data = }} Ав…»

2017-10-22T19:57:41Z

Новая страница: «{{algorithm | name = Адаптивное интегрирование | serial_complexity = | input_data = | output_data = }} Ав…»

Новая страница

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических квадратурных формул[http://algowiki-project.org/ru/Квадратурные_формулы]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «хороших» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

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

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,\frac{a+b}2]</math> и <math>[\frac{a+b}2,b]</math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math><ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>

=== Вычислительное ядро алгоритма ===

=== Макроструктура алгоритма ===

=== Последовательная сложность алгоритма ===

=== Информационный граф ===

=== Ресурс параллелизма алгоритма ===

=== Входные и выходные данные алгоритма ===

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

== Литература ==