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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

Государственное образовательное учреждение

высшего профессионального образования

Московский технический университет связи и информатики

Волго-Вятский филиал.

Кафедра математических и естественнонаучных дисциплин

ЧИСЛЕННЫЕ МЕТОДЫ

(теоретические основы)

Для студентов–заочников 2 курса

направления «Телекоммуникации»

Нижний Новгород 2006

ЧИСЛЕННЫЕ МЕТОДЫ

(теоретические основы)

Составитель .

Издание одобрено на заседании кафедры «___» _____________ 200__ г.

Протокол № ____

1.  Аппроксимация функций методом наименьших квадратов

Пусть дано (I + 1) значений функции y = (x) в (I + 1) различных точках:

yi = (xi), i = .

Требуется построить функцию в виде степенного ряда

F (x; ak, k = ) = = + + … + + … +, которая бы приближалась к (x) с минимальной суммарной квадратической ошибкой

Задача аппроксимации заключается в нахождении значений коэффициентов , при которых сумма квадратов разностей

ri = (xi) – F (xi; ak, k = ) = yi –

будет минимальной (см. рис. 1.1.).

 

r0 y0

r1

ri yi

F (x; ak, k = )

х

 

Рис. 1.1. К определению суммарной квадратической ошибки R (ak, k = )

Минимальное значение R (ak, k = ) будет достигаться при условии

= 0, ,

где – параметр, по которому берется производная.

Таким образом, мы получаем систему (К + 1) уравнений для определения (К + 1) параметров ak, k = .

Рассмотрим данную систему:

С учетом полученного можем записать:

,

или

, ,

где ; .

Запишем данную систему в матричном виде:

G × A = B, где

G = (), ; – матрица Грама;

B = ()т, – столбец свободных членов;

A = ()т, – столбец искомых параметров.

Запишем данные матрицы в развернутом виде:

(1.1)

G = ;

B = ;

А = .

Алгоритм вычисления матриц G и B приведен на рис. 1.2.

Решая эту систему, находим параметры ak, k = , а, следовательно, аппроксимирующую функцию F (x; ak, k = ).

Качество аппроксимации оценивается погрешностью:

.

, i =

 

G, B

Рис. 1.2. Алгоритм вычисления матриц G и B

Пример 1. Требуется получить систему уравнений применительно к функции вида:

F (x; a0, a1, a2) = a0 + a1x + a2x2.

Согласно (1.1) получаем:

G = ;

B = ;

А = .

В развернутом виде система записывается следующим образом:

2.  Решение системы линейных уравнений

Рассмотрим систему (К + 1) линейных уравнений с (К + 1) неизвестными ():

(2.1)

Наиболее распространенным методом решения данной системы является метод Гаусса, заключающийся в последовательном исключении переменных.

Для исключения на i-м шаге итерации () переменной xi используется ведущий элемент и содержащая его ведущая строка (), .

Рассмотрим i-й шаг итерации по исключению переменой xi.

Запишем ведущую и преобразуемую строки:

Для исключения i-й переменной необходимо выполнение равенства:

.

Отсюда .

С учетом этого .

Таким образом, для получения значения элемента для последующего шага необходимо из значения этого элемента на данном шаге вычесть произведение k–го элемента ведущей строки и левого элемента данной строки , поделенное на значение ведущего элемента .

После (К – 1) шага k–е уравнение системы (2.1) преобразуется к виду:

Отсюда может быть найдено значение неизвестной xК:

Указанные преобразования носят название «Прямой ход».

Далее полагая, что все неизвестные xК, xК-1, …, xi+1 вычислены, можно вычислить неизвестную xi. Для этого рассмотрим i-ю ведущую строку:

Отсюда может быть получено:

.

Указанное преобразование носит название «Обратный ход».

Алгоритм поиска решений показан на рис. 2.1.

А (К, К+1)

 

x(k),

Рис. 2.1. Алгоритм решения системы линейных уравнений

Пример. Решить систему уравнений

Выполним 0-й шаг «Прямого хода», т. е. исключаем переменную x0:

Выполним 1-й шаг «Прямого хода», т. е. исключаем переменную x1:

Система уравнений преобразуется к виду:

Отсюда: x2 = = 3.

Далее осуществляем «обратный ход».

2,5 × x1 + 2,5 × 3 = 10; .

2 × x0 + 3 × 1 + 1 × 3 = 10; .

Решение системы: x0 = 2; x1 = 1; x2 = 3.

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

Пусть задана непрерывная функция F (x) и требуется найти корни уравнения F (x) = 0.

Указанная задача распадается на следующие задачи:

-  исследование количества и расположения корней (отделение корней);

-  вычисление интересующих корней с требуемой точностью.

Решение первой задачи основано на следующей теореме:

если непрерывная функция F (x) принимает значения разных знаков на концах отрезка [a, b] (F (a) × F (b) < 0), то внутри этого отрезка существует, по меньшей мере, один корень уравнения F (x) = 0, т. е. такое значение x*, что F (x*) = 0.

Алгоритм отделения корней представлен на рис. 3.1.

(диапазон поиска)

 

нет

 

[х, х + D х] – отрезок, содержащий корень

Рис. 3.1. Алгоритм отделения корней

Сущность методов решения второй задачи заключается в равносильном преобразовании уравнения F (x) = 0 к виду f (x) = x. Равносильным преобразованием уравнения F (x) = 0 называется уравнение f (x) = x, для которого в случае F (x*) = 0 выполняется f (x*) = x*.

Таким образом, нахождения корня x* сводится к нахождению точки пересечения функций f (x) и x.

Процесс нахождения решения заключается в следующем:

берем приближенное значение x0 на отрезке [a, b], содержащем корень и вычисляем первое приближение

x1 = f (x0), далее вычисляем x2 = y(x1) и так далее, xn+1 = y(xn) и так далее.

Для того чтобы итерационный процесс был сходящимся, необходимо, чтобы каждое последующее приближение было ближе к корню, т. е. выполнение условия:

| xn+1 –x*| < | xn –x*|. (3.1)

Учитывая, что xn+1 = f (xn), а x* = f (x*), и используя теорему Лагранжа, можем записать:

f (xn) – f (x*) = f ¢(c) × (xn –x*), где c Î [xn, x*] Î [a, b], т. е. a < c < b.

Следовательно, условие (3.1) преобразуется к виду:

| f ¢(c) × (xn –x*)| < |(xn –x*)|.

Отсюда получаем:

| f ¢(c)| < 1 (3.2)

Итак, для сходимости процесса поиска решения необходимо, чтобы равносильное преобразование удовлетворяло условию (3.2).

Точность решения на n-м шаге может быть определена следующим образом:

D xn = | xn –xn-1|.

Метод решения нелинейного уравнения определяется видом используемого при этом равносильного преобразования. Наиболее распространенными методами являются метод простых итераций и метод Ньютона.

Метод простых итераций

Пусть f (x) = l × F (x) + x.

x0

Тогда, если x* – корень уравнения F (x) = 0, то f (x*) = l × F (x*) + x* = x*.

Таким образом, уравнение l × F (x) + x = x равносильно уравнению F (x) = 0.

Согласно условию (3.2):

| f ¢(x)| = |[l × F (x) + x]¢| = |l × F¢ (x) + 1| < 1,

следовательно

–2 < l × F¢ (x) < 0.

Отсюда следует, что l необходимо выбрать следующим образом:

если F¢ (x) > 0;

если F¢ (x) < 0,

где r = max | F¢ (x)|, x Î [a, b].

x

Графическая иллюстрация метода простых итераций представлена на рис. 3.2.

Рис. 3.2. Метод простых итераций

f (x)

F(x)

x2

x3

x1

x*

a

b

x

x0

Метод Ньютона

Пусть y(x) =

Если F (x*) = 0, то у (x*) = x*. Таким образом, уравнение = х равносильно уравнению F (x) = 0. Согласно условию (3.2):

| f ¢(x)| =, x Î [a, b]. (3.3)

Таким образом, метод Ньютона применим только к функциям, удовлетворяющим условию (3.3).

F (x)

Графическая иллюстрация метода Ньютона представлена на рис. 3.3.

Рис. 3.3. Метод Ньютона

 

Алгоритм решения нелинейных уравнений представлен на рис. 3.4.

x0 Î [а, в]; Е – заданная точность решения

x =f (x0)

равносильное преобразование

 

 

Рис. 3.4. Алгоритм решения нелинейного уравнения

4.  Численное интегрирование

Пусть требуется вычислить определенный интеграл S = .

Разобьем отрезок интегрирования на N равных частей длиной . Точки разбиения определяются следующим образом:

x0 = a + 0 × h, x1 = a + 1 × h, …, xn = a + n × h, …, xN = a0 + n × h = в.

Искомый интеграл может быть представлен в виде:

,

где – интеграл на частичном отрезке [xn, xn+1].

Непосредственное вычисление значений не всегда представляется возможным. Поэтому вместо могут быть вычислены приближенные к ним значения .

Таким образом, можем записать:

.

Способ вычисления величин определяет формулу для численного интегрирования.

1.  Формула прямоугольников

, .

Графическая иллюстрация формулы прямоугольников представлена на рис. 4.1.

Рис. 4.1. Формула прямоугольников

Алгоритм численного интегрирования по формуле прямоугольников представлен на рис. 4.2.

S = h × S

a, в, N

 

2.  Формула трапеций

Графическая иллюстрация формулы трапеций представлена на рис. 4.3.

Рис. 4.3. Формула трапеций

Алгоритм численного интегрирования по формуле трапеций представлен на рис. 4.4.

a, в, N

 

3.  Формула парабол (формула Симпсона)

Графическая иллюстрация формулы Симпсона представлена на рис. 4.5.

Рис. 4.5. Формула Симпсона

Алгоритм численного интегрирования по формуле Симпсона представлен на рис. 4.6.

a, в, N

 

S

Рис. 4.6. Алгоритм численного интегрирования по формуле Симпсона

 

Точность численного интегрирования может определяться по формуле:

,

где SN, – значения интегралов при количестве точек разбиения N и соответственно.

5.  Оптимизация

Оптимизация – это процесс выбора наилучшего решения из множества возможных.

При решении задачи оптимизации рассматривается некоторая величина F (x), называемая целевой функцией. Аргументы x называются параметрами оптимизации.

Результат решения задачи оптимизации – значения параметров, при которых целевая функция достигает экстремума, т. е. минимального или максимального значения. Задача нахождения максимума сводится к задаче поиска минимума и наоборот, поэтому рассмотрим только одну задачу – задачу поиска минимума.

F (x)

F (x)

Указанная задача сводится к построению вложенных отрезков [a1, в1], [a2, в2], …, [ai, вi], …, содержащих точку минимума x*. Процесс получения вложенного отрезка на i-м шаге иллюстрируется рис. 5.1.

x
	F (x)
ai	x

 

 

 

Рис. 5.1. Процесс получения вложенного отрезка

если если ,

если если .

Из рис. видно, что определение границ последующего отрезка происходит следующим образом:

Решение достигается при получении заданной точности Е, т. е. при |вi – ai| < E, и равно .

Способ получения точек x, x определяет метод оптимизации. Рассмотрим следующие методы:

-  метод дихотомии;

-  метод золотого сечения.

Метод дихотомии

При методе дихотомии деление отрезка производится точками, отстоящими от его середины на малую величину h (см. рис. 5.2.) и вычисляемыми по формуле:

h

h

где 0 < h £ 2Е.

D

B

С

А

в

а

x

x

О

 

h

h

C

А

B

D

а

x

в

О

x

x

x

а

C¢

B¢

О¢

D¢

А¢

в

Рис. 5.2. К методу дихотомии

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

а, в, Е

Алгоритм метода дихотомии представлен на рис. 5.3.

 

Рис. 5.3. Алгоритм метода дихотомии

Метод золотого сечения

Метод золотого сечения позволяет сократить количество вычислений целевой функции. При данном методе деление отрезка ai, вi происходит в определенном отношении (см. рис. 5.3.):

l

	x	вi
l1
Рис. 5.4. К методу золотого сечения

 

Определим величину b, для чего обозначим l2 через x:

Используя только положительное решение, получаем:

На каждом шаге, за исключением первого, вычисление значения функции производится лишь в одной точке. Эта точка и называется золотым сечением. Значение функций для другой точки берется из предыдущего шага (см. рис. 5.4.). При методе золотого сечения сокращение величины отрезка на каждом шаге происходит только на величину a = 0,382, т. е. приблизительно на .

 

в

а

x

x

в

а

x

D¢

C¢

B¢

А¢

А	В	С	D

 

а

x

золотое сечение x

в

x

x

а

в

D¢

C¢

B¢

А¢

Рис. 5.5. Определение золотого сечения

а, в, Е

Алгоритм метода золотого сечения представлен на рис. 5.6.

 

Рис. 5.6. Алгоритм метода золотого сечения

ЛИТЕРАТУРА

1.  , Плотников численных методов: Учебное пособие. – 2-е изд., перераб. и доп. – М.: ФИЗМАТЛИТ, 2003. – 304 с.

2.  Волков методы: Учебное пособие. 3-е изд., испр. – СПб.: Издательство «Лань», 2004. – 256 с. – (Учебники для вузов. Специальная литература).

3.  Бахвалов методы (анализ, алгебра, обыкновенные дифференциальные уравнения): Учебное пособие. Том I. – М.: Издательство «Наука», 1973. – 631 с. с илл.