Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - Вычислительная математика - файл 1.docx


Лекции - Вычислительная математика
скачать (1133.7 kb.)

Доступные файлы (1):

1.docx1134kb.15.11.2011 23:51скачать

содержание
Загрузка...

1.docx

Реклама MarketGid:
Загрузка...




ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ


Факультет по работе с иностранными студентами и дистанционным

технологиям

Кафедра физико-математической подготовки


Б. Н. Подболотов


КУРС ЛЕКЦИЙ


по дисциплине «Вычислительная математика»

для студентов заочной (ускоренной) формы обучения

по специальности 230201

«Информационные системы и технологии»


Воронеж 2006



Лекция 1




Введение. Численные методы и приближённые вычисления


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

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

В истории прикладной математики можно различить 3 периода:

1 период 3-4 тыс. лет назад – вычисление объемов, площадей и решение простых задач арифметики, алгебры, геометрии. (жрецы)

2 период начался с Ньютона. Решались задачи астрономии, геодезии и расчета механических конструкций. Задачи сводились либо к решению ОДУ, либо систем линейных алгебраических уравнений (СЛАУ). Бруно, Коперник.

3 период начался с 1940 года, когда надо было быстро рассчитывать, быстро передвигаться, предметы (катюша), зенитные орудия и т.д.

Курчатов, Сахаров, Королев, Появились ЭВМ.

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

Не следует думать, что знание численных методов и новых ЭВМ позволяет сразу решить любую задачу.

Решение сложной инженерной задачи выполняется в следующей последовательности.

Формулируется конечная цель решения, выявляются исходные и получаемые параметры.

Система отношений, связывающая исходные и конечные параметры.

Позволяет по исходным данным найти исходный результат. Составляется схема последовательных действий (алгоритм).


Тот же алгоритм, но записанный на языке «понятном» для ЭВМ.


При построении математической модели 

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

Раздел вычислительной математики состоит из следующих частей:

  1. Общие понятия об интерполировании функции. Численное интегрирование и дифференцирование.

  2. Решение СЛАУ.

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

  4. ОДУ.

  5. Задачи на собственные решения.



^

Методы решения


Методы решения задач делятся на аналитические, графические и численные.

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

^

Абсолютная и относительная погрешность.


Пусть α- точное значение некоторой величины, αn- известное приближенное к этому точному значению. Абсолютной погрешностью приближения α называется величина

или αn= α ± ∆α

Абсолютная погрешность далеко не всегда может охарактеризовать эффективность метода получения приближённого результата: например

∆α= 1 мм при измерении расстояния в 1 км или диаметра вала 4 мм, имеют совершенно различную характеристику качества измерения. Поэтому часто пользуются относительной погрешностью

или

Часто используют относительную погрешность выраженную в %.

^

Погрешность арифметической операции


Арифметические действия над приближенными числами приводят к накоплению погрешности результата решения математической задачи. Пусть α, в, αn и вn – некоторые числа и их приближенные значения, α◦в- некоторая арифметическая операция над числами. Тогда абсолютную и относительную погрешности арифметических операций будем записывать в виде



При этом если ∆α >0 и ∆b>0, то


Используя данные результаты можно оценить и относительные погрешности


δ(αn)=nδα

При оценке погрешности вычисления функций y=f(x) для придельных значений абсолютных и относительных погрешностей используем равенства


где xn- приближённое значение величин х, ∆x- придельная погрешность.

Алгоритмы являются строгим описанием последовательности операций. Общие свойства алгоритмов:

  1. Массовость- применимость ко всем задачам рассматриваемого класса при любых исходных данных или с оговариваемыми границами их изменения.

  2. Определенность- любой шаг алгоритма не должен допускать толкования.

  3. Дискретность- представимость всякого процесса в виде последовательности выполняемых друг за другом отдельных законченных шагов.

  4. Результативность- получение результата за конечное число действий, причем с требуемой точностью.



^

Лекция 2




Общие понятия об интерполировании.


Рассмотрим следующую задачу. Пусть функция f(x) задана таблично, т. е.

известны её значения в (n+1) – точках xi Є[a,в], где i=0,1,2…n f(xi) =yi




Точки x0x1x2…xn называются узлами интерполяции. Требуется найти простую функцию φ(х), что φ(xi)= f(xi) в узлах интерполяции и φ(x)≈ f(x) в остальных точках х.

Пусть -последовательность вещественных функций. Тогда называется обобщенным полиномом.

Обобщенный полином называют интерполяционным, если f(xi)= φ(xi) i=0,1,2… в узлах интерполяции. Обычно в качестве {φi(x)} берутся функции.

  1. 1, х, х2, х3

  2. 1, sinx, cosx, sin2x, cos2x…

  3. 1, eλ1х, eλ2х, eλ3х

λ1 λ2 …λn- некоторая последовательность.


^

Линейная интерполяция.


При линейной интерполяции предполагается, что функция f(x) между узлами интерполяции изменяется по линейному закону (см. рис)


из геометрии уравнение прямой, проходящей через точки (xi-1 yi-1) и (xi yi) будет иметь вид (



Отсюда для каждого x, лежащего в интервале [xi-1 xi ] может быть найдено соответствующее значение y по формуле

Таким образом, мы можем найти любое f(x) =y на любом отрезке интерполяции.

^

Интерполяционный многочлен Лагранжа.


Точность аппроксимации можно повысить, если вместо линейной функции использовать алгебраический многочлен

Ln(x)= a0+ a1x+a2x2+…+ anxn

Будем искать его в виде.

(1)

где φj (x) – многочлен n, который удовлетворяет условия


В n точках полином обращается в нуль и только в одной точке i=j обращается в 1. Раз он обращается в нуль в n точках, то в нем должен быть множитель

φj (x)=Сj (x-x0 )(x-x1 )…(x-xj-1 )(x-xj+1 )… (x-xn ) (2)

где Сj – неопределенный коэффициент.

Надо потребовать, чтобы в точке i=j он обратился в 1

1=φj (xj)=Сj (x-x0)(x-x1 )…(x-xj-1 )(x-xj+1 )…(x-xn )

и тогда

(3)


Или подставляя (3)→(2) получим

(4)

Подставляя (4) в (1) получим

(5)


Lj (n)(x)

Полученный полином называют интерполяционным полиномом Лагранжа.

Если ввести обозначение ωn+1(x)= (x-x0)(x-x1)… (x-xn ), то полином Лагранжа заменяется в виде:

(6)


Lj (n)(x)


Тогда φj (x) и Lj (n)(x) называются Лагранжевыми коэффициентами. Составление полинома Лагранжа и вычисление его в отдельных точках в ручную довольно таки трудоемкая задача. Добавление лишнего узла приводит к пересчету всех коэффициентов. Остаточный член интерполяционной формулы Лагранжа выглядит так

(7)

Тогда

f(x)= Ln(x)+ Rn(x)

^

Оценка погрешности интерполяционной формулы Лагранжа




R(x) = f(x)-Ln(x)

Будем считать, что f(xi) – вычислены точно. Тогда . Если f(x) полином степени меньше или равной n, то при любых x . Пусть f(x) (n+1) раз дифференцируемая на отрезке [a,b] функция.

Рассмотрим вспомогательную функцию . Очевидно, что i = 0,1,2,…,n в (n+1) точках. Подберём k таким образом, чтобы в точке в которой мы хотим оценить полином , т.е. и тогда (1). При данном выборе k функция g(z) обращается на [a,b] в нуль в (n+2) точках . По теореме Роля производная g’(z) обращается в нуль на [a,b] в (n+1) точке и т.д. Производная (n+1) порядка от g(z) обращается в нуль по крайней мере 1 точке [a,b]. Обозначим через эту точку, тогда

(2)

или

и тогда

(3)

где , тогда

(4)

Последняя формула позволяет заранее оценить отклонения функции Ln(x) и выбрать нужное количество узлов n.

^

Исследование остаточного члена при равноотстоящих узлах.



При интерполировании функций желательно, чтобы модуль Rn(x) принимал наименьшее значение. Поэтому нужно исследовать следующие вопросы.

  1. При заданных узлах интерполяции, изучить для каких участков [a,b] остаточный член Rn(x) будет принимать max и min значения.

Поведение первого сомножителя в остаточном члене в зависимости от изменения x нам не известно. Тогда для решения задачи мы можем лишь следить за поведением функции при заданных узлах . Полином обращается в нуль в точках и меняет знак при переходе через каждый узел. Между узлами имеет место min и max.

Естественно ожидать, что вблизи больших по модулю экстремумов будет большая погрешность Rn(x).

Поведение можно исследовать в случае равноотстоящих узлов , положив и тогда

1)

2)

Т.к. при , то

при , то

Тогда экстремальные значения на отрезке [k,k+1] будут max по абсолютной величине на крайних точках [0,1], [n-1,n] и min в середине, следовательно имеет следующий примерный график




Следовательно, ошибка интерполяции меньше на середине отрезка и больше к концам отрезка. Вне отрезка [a,b] будет возрастать.

^

Лекция 3



Методы приближенного интегрирования.

Формулы Ньютона –Котеса.



Один из методов приближенного интегрирования f(x)d(x) заключается в замене функции f(x) на какой- либо интерполяционный полином. Например


В этом случае, если взять узлы интерполяции равноотстоящими, то

xk=x0+k*h k=0,1,2…n

x=x0+t*h dx=hdt


x-x0=(x0+th)-(x0+0h)=th

x-x1=(x0+th)-(x0+1h)=(t-1)h

_ _ _ _ _ _ a=x0=x0+tht=0

x-xn=(x0+th)-(x0+nh)=(t-n)h


xk-x0=(x0+kh)-(x0+0h)=kh

_ _ _ _ _ b=xn=x0+nh=x0+nht=n

xk-xk-1=(x0+kh)-(x0+(k-1)h)=1h

xk-xk+1=(x0+kh)-(x0+(k+1)h)=-1h

_ _ _ _ _ _

xk-xn=(x0+kh)-(x0+nh)=-(n-k)h


dt*f(xk)= An(k)f(xk)h


…dx=(b-a)n

[a, b]
^

Частные случаи.


n=1 L1(x)=ax+ b


A1(0)=- dt=

A1(1)=dt=

f(x)dx=h()=

f(x)dx== h[]

n=2 L2(x)=a2 x+ b+c


A2(0)=- dt=



A2(1)=dt=

A2(2)=dt=


f(x)dx=h()=

f(x)dx== =[]

^

Лекция 4




Численное дифференцирование.


Напомним, что производной функции y=f(x) называется предел отношения приращения функции ∆y к приращению аргумента Δx при стремление Δx к нулю

y`= f `(x)= ∆y= f(x +Δx )- f(x) (1)

В численных расчетах на ЭВМ, когда функция задана таблицей значений, значение шага Δx полагают равному конечному числу и для вычисления значений производных получают приближенное равенство

y`≈ (2)

Это соотношение называется аппроксимацией производных с помощью отношения конечных разностей (т.к. ∆y и Δx конечные в отличие от значений в формуле (1)).

Рассмотрим аппроксимацию производной для функции y=f(x), заданной в табличной форме xi= x0, x1… xn yi= y0, y1… yn

Пусть шаг разности между соседними значениями аргумента постоянен и равен h. Запишем выражение в точке x=x1

∆x=h

(3)





0(h)

~0(h)

~0(h2)

~0(h2)

Можно найти производные с помощью формул Тейлора

f(x +Δx )= f(x)+


(1) y(xi-1 )=y(xi –h) = y(x)- hf `(xi )+0(h2)

yi-1= yi- hf `(xi )+0(h2)

y`(xi)=f `(xi)= ~0(h)

(2) y(xi+1 )=y(xi +h) = y(x)+ hf `(xi )+0(h2)

yi+1=yi+ hf `(xi )+

y`(xi)=f `(xi)= ~0(h)

  1. y(xi-1 )=yi –h yi `++ 0(h3)

  2. y(xi+1 )=yi +h yi `++ 0(h3)

(1)+ (2)

yi-1+ yi+1=2 +

=~0(h2)

(2)- (1)

yi+1 -yi-1 =2hyi `

yi `=~0(h2)

Можно использовать полиномы Лагранжа и Ньютона.

^

Метод неопределенных коэффициентов.




a=-b=-


=

И так далее.

Лекция 5




Разделённые разности



Пусть функция f(x) вычислена в точках i=0,1,2,…,n, . Тогда выражение

называется разделённой разностью 1-го порядка.

Разность вида: называется разделённой разностью 2-го порядка

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -



Разность вида: -называется разделённой разностью к-го порядка. Вычисляются разделённые разности согласно Таблицы №1.


Таблица №1


1) Разделённые разности симметричны относительно своих аргументов

т. е. узлы можно менять любым образом.

2) Разделённые разности порядка k от являются однородным многочленом относительно своих аргументов степени n-k , при n=k она равна 1, а при k>n она равна 0.





1

0

1 0

0

1


3) Линейность разделённой разности относительно функции, к которой применяется разделённая разность.


^

Интерполяционный полином Ньютона для неравно отстоящих значений аргумента




Пусть f(x)  некоторая функция, а x0,x1,…xn  узлы интерполяции, а x  произвольная, но фиксированная точка значения аргумента. Тогда имеем:


=

Откуда:


Аналогично:


Откуда


продолжая этот процесс далее, получим:


Эта форма записи носит название интерполяционной многочлена Ньютона для неравных промежутков или


полином n-степени, остаточный член.


Можно показать, что полином Ньютона и полином Лагранжа совпадают Nn(x)= Ln(x), т.е. равный их остаточный член.

Или

Полином Ньютона удобнее полинома Лагранжа тем, что при добавлении новых узлов интерполяции все проведенные вычисления в полиноме Ньютона сохраняются, а в полиноме Лагранжа нет.
^

Конечные разности.


В случаях когда узлы интерполяции берутся равноотстоящими

xk=x0+k*h k=0,1,2…n

n- шаг интерполирования, то часто вводят следующие обозначения

– конечные разности


0нисходящие

восходящие - конечная разность 2го порядка

центральные



- конечная разность 3го порядка


^

Связь конечных разностей и разделенных разностей.


Для равностоящих значений аргумента xk=x0+k*h имеем:


_ _ _ _ _ _ _ _ _ _


Интерполяционный полином Ньютона для равноотстоящих значений аргумента.


Если в общей формуле полинома Ньютона

Nn(x)= f (x0)+ f (x0 x1)(x-x0 )- (x-x0 )(x-x1 )f (x0x1xn)+

…+….+(x-x0 )… (x-xn-1 )f (x0x1…xn)+(x-x0 )…(x-

xn )f (x0x1…xn) (1)

В качестве узлов интерполирования можно взять xk=x0+k*h и положить

x=x0+t*h k=0,1,2…n, то тогда

x- xk=( x0+th)- (x0+kh)= (t-k)h и

и мы получим полином Ньютона для интерполирования вперед.


Эта формула применяется при вычислении в начале таблицы разности.

Если в уравнении (1) в качестве узлов взять xk=x0+k*h и ввести замену

x=x0+t*h, то получим

x-xk=(x0+th)-(x0-kh)=(t+k)h



то получим полином для интерполирования назад.


Эта формула применяется для интерполирования в конце таблицы.


^

Лекция 6




Классификация уравнений. Этапы численного решения.


Любое уравнение может быть записано в следующем общем виде

f(x)=0.

Если f(x) – алгебраическая функция (например, f(x)=x4+2x-1, f(x)=), то уравнение называют алгебраическим. Всякое алгебраическое уравнение может быть преобразовано к виду

a0 xn + a1 xn-1 +…+ an-1x + an=0. (*)

Если f(x) не является алгебраической (содержит степенную, логарифмическую, функцию sin, cos и т.д.), то уравнение называют трансцендентным (например, f(x)=2x + lnx - 6) .

Решить уравнение – это значит найти такие значения x, (которые называют корнями уравнения), при которых заданные уравнения обращается в тождество.

При численном приближённом решением уравнения выделяю 2 этапа:

  1. отделение корней – отыскание достаточно малых интервалов, в каждом из которых один и только один корень уравнения;

  2. вычисление каждого корня с заданной точностью внутри выделенного интервала.



^

Отделение корней.


Пусть [a, b] – интервал изменения х, в котором отыскиваются вещественные корни уравнения f(x)=0, где f(x) – непрерывная функция вещественного переменного. Разбив [a, b ] на n отрезков длинной , наличие простого корня в интервале [xk-1, xk], k=1, 2, … , n, легко установить по знаку произведения концевых значений функции f:


Алгоритм определения корней можно показать следующей блок схемой (см. лист 9). Алгоритм предусматривает ввод (блок 1) исходных данных (a, b – начало и конец исследуемого интервала, n – число одинаковых отрезков разбития [a, b] на подынтервалы) и определение величины (блок 2). Далее для каждого интервала длиной вычисляется (блок 3) и y=f(xk) (блок 7), а затем, в результате исследования знака произведения (блок 8), решается вопрос о существовании на простого корня. При предусматривается выдача значений границ (блок 9) и выявление начала следующего интервала (блок 10).


Если отказаться от блока 10, то при случайном совпадении корня с точкой xk деление отрезка произойдёт выдача на печать значений двух интервалов и , хотя нам достаточно одного.

При определении корней алгебраического уравнения (*) можно воспользоваться следующими закономерностями:

а) алгебраические уравнения п – го порядка имеет п корней, среди которых могут быть вещественные и комплексные;



b) число положительных вещественных корней равно числу (или меньше на чётное число) перемен законов в последовательности коэффициентов a0, a1 , a2 , … , an , причём равные нулю коэффициенты не учитываются (теорема Декарта).


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

^

Метод половинного деления (бисекций).




Пусть простой корень х* уравнения f(x)=0 определён и находится на отрезке [c, d], т.е. f(c)f(d)<0, причём , где - допустимая погрешность вычисления. Возьмём в середине [c, d] точку . Очевидно, что при точка х*q будет искомым корнем уравнения. В противном случае сделаем первый шаг к уточнению корня.



Вычислим . Если=0, то корень уравнения . Если (рис. а), то х* лежит внутри интервала , который обозначим как . Если , то х0 лежит в нутрии , который обозначим как (рис. б). В обоих случаях длинна отрезка равна

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


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

Блок схема алгоритма метода бисекций:


^

Метод итераций.


Приведём уравнение к виду (1)

Возьмём некоторую произвольную точку на оси . Если существует такая точка , что , то очевидно, число и будет корнем уравнения (1). В общем случае . Суть метода простых итераций (повторений) состоит в построении последовательности {} точек, сходящихся к корню , где , (2)

При этом называют начальным приближением.


Необходимо отметить, что последовательность {} не всегда является сходящейся. Рассмотрим пример:

Линейное уравнение , имеющее корень можно преобразовать к виду или .

Взяв за начальное приближение , в первом случае получим

; , …

Данная последовательность стремится к точному решению уравнения.

Во втором случае

; ; , …

Эта последовательность расходится.

Следовательно, вид функции оказывает существенное влияние на сходимость итерационного процесса.

Сходимость метода простой итерации определяется следующей теоремой: ^ При любом начальном приближении на некотором интервале последовательность, построенная в соответствии с методом простой итерации (2), сходится к корню , который является единственным решением уравнения (1) на рассматриваемом интервале, если здесь функция удовлетворяет условию Липшица


с постоянной Липшица .

Если функция дифференцируема и имеет на ограниченную производную, то постоянная Липшица .



В рассмотренных выше примерах для уравнения и итерационный процесс является сходящимся к корням уравнения .

Для уравнения и условия сходимости не выполняется.

Если вычисление постоянной Липшица сопряжено с определёнными математическими трудностями, то алгоритм метода простой итерации использует косвенную оценку точности вычислений

,

где - допустимая погрешность вычислений.

Блок – схема алгоритма метода простой итерации с косвенной оценкой точности вычислений:


^



Лекция 7




Метод ньютона (касательных).


Если уравнение имеет корень и непрерывную производную на отрезке , то функцию можно выбрать в виде

.

В результате задача определения корня уравнения сводится к отысканию корня уравнения

. (1)

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

(2)

Построим график функции . Уравнение касательной в точке будет иметь вид


Найдём точку пересечения этой касательной с осью у. Так как при , то

Тот же результат получим из соотношения (2) при . Следовательно, первое приближение корня можно найти и геометрически с помощью касательной к графику функции в точке . 

Аналогичным путём можно построить второе и последующие приближение. Отсюда название метод касательных.

Следует отметить, что при сходимость алгоритма метода Ньютона будет наблюдаться при любых начальных приближениях в интервалах .

При сходимость итерационного процесса будет обеспечиваться при выборе начального приближения из условия

,

где m, Mнекоторые положительные константы, для которых

,

для всех .

Приведём алгоритм решения уравнения методом Ньютона в виде блок – схемы:


Метод Ньютона обеспечивает более быструю сходимость, чем метод простой итерации.

В заключение следует отметить, что при решении нелинейных уравнений

^

Численные решения СЛАУ.

Метод Гаусса.


Пусть задана система линейных уравнений Ax=U с плотной матрицей, элементы которой хранятся в оперативной памяти.


Переходим к системе (исключения х1)


Эта операция равносильна умножению Ax=U слева на матрицу


где pi1= i=2,3…n A1 x= U1 Ax= U

aij(1)= aij- aij

Следующий переход к системе (исключения х2)



Это исключения равносильно умножению A1 x= U 1 слева на матрицу Р2:


где pi2= i=3,4…n aij(2)= aij(1) - a2j(1)

A1 x= U1=> A1х =U1P2P1Ax= P2P1 U

Продолжая этот процесс и так далее, мы придем к легко решаемой системе уравнений с треугольной матрицей An-1х =Un-1


An-1 =


An-1- верхняя треугольная матрица. Здесь An-1х=Un-1=> =Pn-1Pn-2Ax= Pn-1Pn-2 U, так что A =(Pn-1Pn-2 …P1)-1 An-1х


P Q


A = *


Где матрица P- нижняя треугольная, а Q- верхняя треугольная. Решение по методу Гаусса сводится к разложению A на произведение двух треугольных матриц. Одна из них

P~ с единицами по главной диагонали и на верхнюю треугольную


Q~


Заметим, что

det A=det P*det Q= a11 a22(1) a33(2)… ann(n-1)

Если представления матрицы A в виде PQ найдены, то решение системы Ax=U сводится к решению двух треугольных систем уравнений.

Py= U ↓ (y)

Ax=U=>PQx=U=>



Qx= y ↑ (x)

Решения по методу Гаусса сводится фактически к решению системы Py= U ↓

При прямом ходе, а затем к решению системы Qx= y ↑ при обратном ходе.

Разложение матрицы на две треугольные матрицы называется процессом факторизации (триангуляция) матрицы, т.е. представление матрицы в виде A=PQ.

После вычисления прямого хода мы получаем матрицу An-1= Q

Метод Холецкого, прогонки приводят к факторизации матрицы A.


Метод Холецкого.

Пусть дана невырожденная матрица размером N*N (det A≠0) Представим её в виде произведения

A=BC (1) A~(aij) B~(bij) C~(cij)


k>i


bik=0, когда k>i


ckj=0 при k>j cjj =1

Из (1) следует

aij=bik cki

Преобразуем эту сумму двумя способами

aij=bik cki= bik cki+ bii cij+bik cki= bik cki+ bii cij


aij=bik ckj= bik ckj+ bij cjj+bik ckj= bik ckj+ bij cjj bij cjj= aij- bik ckj

Отсюда находим

bij= i ≥ j b11=a11 cjj=1

cjj= при I < j



Матрицы B и C найдены, тогда Ax= BCx=U

By=U ↓ (y) прямой ход


Cx=y ↑ (x) обратный ход


^

Лекция 8

Метод прогонки.


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

Пусть требуется найти решение следующей системы трехточенных уравнений.


Или в векторной форме

A (2)


A=


По методу Гаусса A= * = *

Факторизация ленточных матриц, т.е. разложение их на произведение двух треугольных матриц A=PQ

(нижней и верхней) треугольных матриц может быть произведено так, что P и Q также будут ленточными матрицами.



Перейдем к следующей системе (3)

yj=pj+1yj+1+qj+1 (3)

Где pj+1 и qj+1 неизвестные числа


u0- p1u1 =q1

u1- p2u2 =q2 =

u0- p1u1 =q3


Числа pj и qj можно искать из системы (1), т.к.

yj-1=pjyj+qj (4)

Подставляя (4) в систему (1) получим

-aj(pj yj+ qj)+cj yj-bj yj+1=fj

(cj-aj pj)yj=bj yj+1 +(fj+ aj qj)

(5)

Сравнивая (5) с(3) получим

(6)

Из 1го крайнего условия

y0 =p1y1+q1

=> (7)


Из 2го крайнего условия

yn-1= pnyn+qn

-an yn-1+cnyn=fn (8)


Теперь с помощью (3) получим




Проверка метода прогонки на устойчивость.

Поскольку вычисления pj и qj производятся по рекуррентным формулам, то в зависимости от элементов матрицы A: ai, bi, ci, то неизбежны ошибки округления при вычислении по рекуррентным формулам pj и qj. Эти ошибки могут быстро возрастать и сделать вычисления непригодными. Поведение ошибки dpj+1 можно проследить, положив её приближённо равной дифференциалу функции.


Имеем

(9)

Прогонка будет устойчивой, если и (10)

Тогда dpj+1 <dpj

Эти неравенства (10) будут выполнены, если, например, положить, что коэффициент матрицы A удовлетворяют следующие условия

0≤ aj≤bj

cj≥ aj+bj (11) j=

0<

В самом деле

, отсюда

<

Вообще, проверяется pj+1≤ 1 для j=1,n-1

При этих условиях при вычислении pj+1 накопление ошибки не происходит. Аналогично из равенств

;

<dqj

Т.к. при тех же условиях (11) нарастания погрешностей при вычислении q j+1 не происходит.

^

Лекция 9

Метод конечных разностей решение краевых задач ОДУ.


Пусть дана краевая задача ОДУ





Требуется решить такое уравнение. Отрезок [a, b] разбивается точками на равные части xj=x0+jh. Точки разделяются на внутренние 1 ≤ j ≤ n-1 и граничные j=0 и j=n. Затем производные входящие в уравнение (1) заменяются в точках хi приближенными конечно-разностными соотношениями.

y`(xi)= ~0(h) (*)

=~0(h2)

=~0(h2)

И подставим равенства (*0 в уравнение (1), получим

(2)


Преобразуем (2) к виду (3), получишь

(3)


c0 y0- b0 y1…………………..=f0 j=0

(4) ……-aj yj-1+cj yj-bj yj+1….......=fj 1≤ j≤ n-1

………………...-an yn-1+cnyn=fn j=n


Или



=

Полученную систему решаем методом прогонки, которую мы рассматривали в системах линейных уравнений.


^

Лекция 10




Сплайны.


Пусть есть функция f(x) заданная в узлах отрезка [a,b]. Пусть заданны узлы интерполяции x0x1…xn xi[a,b] в которых заданны значения функции f(x0) f(x1)… f(xn) [x0x1], [x1x2]… [xn-1xn]~∆- разбиения.

Будем приближать функцию f(x) на каждом отрезке ∆~[xj-1xj] полиномом

Pj,m(x)=a0j+a1jx+…+ anjxm

Сплайном назовем S(x) функцию совпадающую на каждом участке [xj-1xj] с полиномом Pj,m(x) и такую, что во всех внутренних узлах непрерывную вместе со своими производными до (m-1) порядка включительно во всех точках xi i=1, n-1.
^

Кубический сплайн.


Будем считать, что на каждом участке [xj-1xj] мы приближаем полином 3=ей степени.

Pj,3(x)=ax3+bx2+cx+d, тогда

(1)

Найдем S(x) для чего проинтегрируем дважды (1), получим


Найдем с1 и с2 из условия S(xj-1)= y j-1 S(xj)= y j



C1hj=yj- Mj=> C1hj=yj-yj-1+

C1=

C2=


Поскольку S`(xj-0)= S(xj+0)


Приравнивая получаем


(2)

λj= μi= λj+ μi=1

μiMj-1+2Mj+ λj Mj=dj j=1,n-1

Полученная система служит для определения M0 M1… Mn, подставляя в формулы (х) и (х*) получим, что полином удовлетворяет 3-м свойствам

  1. S(xj-0)= S(xj+0)

  2. S`(xj-0)= S` (xj+0)

  3. S``(xj-0)= S``(xj+0)



^

Лекция 11

Абсолютная величина и норма матрицы.


Под нормой матрицы A~(aij) понимают действительное число , удовлетворяющее следующим условиям:

  1. (=0 тогда и только тогда, когда A=0)

  2. где α- число.





Матрица определяется тремя нормами.









Для матрицы


Найти

Решение







Для вектора эти нормы вычисляются по следующим формулам

  1. -максимальная из координат вектора взятая по модулю

  2. - сумма модулей координат вектора

  3. -корень квадратный из суммы квадратов модулей координат вектора

Пример.

Вычислить

Решение





^

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


Пусть задана система линейных уравнений

Ax=b=>Ax-b=0 (1) Ax`-b=ξ- невязка

x- x+ Ax-b=0=>x= (I-A) x+ b=>x=Bx+ b (2)

Пусть матрица B невырожденная, т.е. det B≠0/

Выбрав произвольно x0 вычисляем последовательно xk

xk= Bxk-1+b (3)

Пусть x*- точное решение уравнения (1) и (2), тогда


(xk-x*) =B (xk-1-x*) (4)

(xk-x*) =B (xk-1-x*) = B B (xk-2-x*) = Bk (x0-x*) (4a)

Пронормируем последнее выражение (4а) получим:

(5)

Из полученного неравенства следует, что при произвольном выборе x0 соотношение (6) при < 1 (7)

Эквивалентно или . Соотношение (6) возможно, если выполнено неравенство (7). < 1
^

Оценка погрешности метода простой итерации.


х*= Bx*+b

xk= Bxk-1+b

Рассмотрим выражение

(1) (I-B)(x*-xk)=x*-xk-Bx*+ Bxk= -xk+b+ Bxk=xk+1-xk

(I-B)(x*-xk)= xk+1-xk

(x*-xk)= (I-B)-1(xk+1-xk) (2)

Пронормируем выражение (2) получим

(2а)

Найдем

Рассмотрим для этого тождество

(I-B)(I-B)-1=I

(I-B) -1- B (I-B)-1=I

(I-B) -1=I+ B (I-B)-1

(3)


xk+1- xk= B (xk-xk-1) = B B (xk-1-xk-2) = Bk (x1-x0) (4)

Подставляя (3) и (4) в формулу (2а) имеем

(5)

Эта формула позволяет подсчитать число итераций необходимое для получения приближения с заданной точностью.


^

Лекция 12

Приведение систем к виду, допускающему применение метода простых итераций.


Обычно система линейных уравнений задана в виде


и для приведения её к виду x=Bx+b, допускающего применение метода простых итераций. Подбирают невырожденную матрицу H (det H≠0), так чтобы

Ax=b => HAx= Hb=> x- x+ HAx= Hb=>

X= x- HAx +V=> x= (I-HA)x+ V

Берем B=I-HB

Тогда получаем x= Bx+ V, причем

Матрицу H целесообразно близко к A-1 так, чтобы HA~I. Так, например, если в матрице A вдоль главной диагонали элементы преобладают над остальными, то берут


Если матрица A=A* самосопряженная и положительно определенная A*=A и λ у матрицы A положительна, у которой известны её max и min собственные значения.




0≤ m≤M, то полная H= tI получим


Т.к. надо найти , то



  1. -(1-tm)=-(1-tM)

  2. 1-tm=1-tM

  3. -(1-tm)=(1-tM)

  4. 1-tm=-(1-tM)

  1. и (4) 1-tm=-(1-tM)=>2=t(M+n)=>t=

(1) и (2) 1-tm=1-tM=> t(M-m)=0 t=0 это не берем

Тогда

х*= Bx*+b

xk= Bxk-1+b

x*-xk=B(x*-xk-1)=BB(x*-xk-2)=…=Bk(x*-x0)

Получим max скорость сходимости

Пример простой итерации решить систему


Пример

Приведем систему к нормальному виду x=Bx+V


x=Bx+ V





=


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


Тогда x1=2,9935 x2=1,0068 x3=1,0068

Или x1≈3 x2≈1 x3≈1
^

Метод Зейделя.


Решение системы Ax=U по методу Зейделя производится по формулам


Если при вычислении i-той координаты вектора

учитывается найденные заранее уже координаты …



То вычисления будут проходить по формулам Зейделя.


^

Лекция 13

Методом Зейделя решить систему


7,6x1+0,5x2+2,4x3=1,9

2,2x1+9,1x2+4,4x3=9,7 Ax=U

-1,3x1+0,2x2+5,8x3=1,4

Решение приведем систему к виду, допускающему применение итерационных методов x =Bx+V



  1. За нулевые приближение возьмем

  2. Строим процесс по методу Зейделя.

-1-ая приближенность

Второе приближение


Решение приводим в таблице

N итерации

X1

X2

X3

0

0,19

0,97

-0,14

1

0,2207

1,0703

-0,1915

2

0,2354

1,0988

-0,2118

3

0,2424

1,1088

-0,2196

4

0,2454

1,1124

-0,2225

5

0,2467

1,1138

-0,2237

6

0,2472

1,1143

-0,2241

7

0,2474

1,1145

-0,2243

8

0,2475

1,1145

-0,2243




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

x1≈0,247 x2≈1,114 x3≈-0,224

Проверим, сходиться ли метод Зейделя для данного примера


Сходится, т.к. =0,75<1
^

Обусловленность систем линейных уравнений число обусловленности.


Задача над плохо обусловленной, если вычисляемые величины X очень чувствительны к небольшим изменениям исходных данных. Рассмотрим причины, определяющие решения X систем Ax=U (1)

Изменим правую часть U на U+δU, это приведет к изменениям решения x на x+δx и при постоянной матрице A, имеем:

A(x+ δx) = U+δU (2)

Из (1) (3)

Из (2) имеем Aδx=δUδx=A-1δU=> (4)

Перемножим (3) и (4) получим

(5)

Число k(A)= называют числом обусловленности. Если число k(A) велико, то для большинства правых частей решение ненадежно. Это же число может быть использовано и для других задач. Пусть, например, δх – погрешность вызвана погрешностью δА элементов матрицы А, а правые части заданны точно, тогда имеем

(A+ δA)( x+ δx)=U

Из (1) имеем x=A-1U (6)

x+ δx= (A+ δA) -1U (6a)

A-1U+ δx= (A+ δA) -1U=> δx= [(A+ δA) -1- A-1]U=> (7)

(A+ δA) -1- A-1=[I- A-1 (A+ δA) ] (A+ δA) -1=-A-1δA(A+δA)-1

Подставляя в (7) получим

δx=-A-1δA(A+ δA) -1U

δx=-A-1δA( x+ δx)

(8)

Число обусловленности обладает рядом свойств

  1. k(CA)=

  2. 

  3. k(A)=k(A-1)

  4. k(A)= k(A)≥1

  5. Если m-min значение матрицы; M-max значение матрицы, то

и

Отсюда следует наличие малого собственного значения матрицы А обязательно означает её плохую обусловленность. Однако матрица А может быть плохо обусловленной, когда у неё нет малого собственного значения. Например, наименьшее собственное значение матрицы 100го порядка

Равен m=0,501. Если же рассмотреть систему Ax=U c , где , то имеем


То получим


Первая компонента решения Ax=U система больше, чем 1022, т.е.

Отсюда

В свою очередь для любой матрицы

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

Матрица плохо обусловлена

Пример

Рассмотрим систему

Точное решение x=1 и y=1

В рассматриваемом примере матрица системы AX=U симметрична и имеет собственное значение



m=0,00005

M=1,98005

Здесь

Система плохо обусловлена, а значит следует ожидать, что малые значения (сдвиг) правых частей приведут к большому изменению решения

, т.е. рассмотрим систему

x+0, 99y=1, 989903

0, 99x + 0,98y=1,970106

То получим решение x=3,000 y=-1,0203, т.е.

Здесь

Значит небольшое изменение δU влечет за собой изменение относительной погрешности вычислительных величин на 200%. Задача плохо обусловлена.
^

Лекция 14




Численные методы решения задачи Коши для ОДУ.


Пусть имеем уравнение n-го порядка

Y(n)=f(x,y,y`…y(n-1)) (1)

Y(xk)=y0(k) k=0,1,2…n-1

Эта задача сводится следующей системе дифференцированных уравнений первого порядка


Тогда


Тогда уравнение (1) запишется



(2)

Пример


Тогда

(2)

Запишется в виде (2)
^

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


Пусть есть (1)

Решение можно записать в виде ряда Тейлора


Здесь Y(k)(x0) заданы начальными условиями.

Пример


^

Метод Эйлера


(1)

Этот метод получается, если в формуле Тейлора удержать только 2 числа первых.



По этому методу интегральная кривая заменяется на касательную к интегральной кривой. Этим методом находится решение на отрезке [x0,x0+h] затем счет повторяется.


Найденные точки ломаной M0M1…MN позволяет построить ломаную, называемой ломаной Эйлера. Точность метода 0(h), остаточный член 0(h2). Чем меньше возьмем h, тем точнее будет результат.

^

Лекция 15

Метод Рунге - Кутта


Один из наиболее употребительных методов с повышенной точностью является методов Рунге – Кутта. Мы будем рассматривать этот метод для уравнения 1-го порядка.

(1)

Если правая часть уравнения непрерывна в окружности точки (х0у0) то решение задачи Коши может быть представлено в виде ряда Тейлора.

(2)

Будем искать решение

(3)

ξ00 η00

ξi=x0 +aih ηi=y0+

и будем рассматривать функцию

φr(h)=

Причем Pri, ai и βij- некоторые const подлежащие определению и определяются так, чтобы

φr(e)(0)=0 e=0,1,2…s φr(s+1)(0)≠0

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


r=1


Таким образом, это совпадает с формулой Эйлера. Точность 0(h’), а отличается 0

r=2


Система имеет 4 неизвестных и 3 уравнения, т.е. имеет бесчисленное множество решений

Если положить то

и тогда какие решения или до

^



Лекция 16




Эмпирические формулы



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

























Задача состоит в том, чтобы найти приближённую зависимость y=f(x) (1)

Значение которой при (i=0,1,2…n) мало отличается от остальных данных. Приближённая функциональная зависимость (1), полученная на основании экспериментальных данных, называется эмпирической функцией.

Будем считать что тип эмпирической формулы выбран и её можно привести в виде: (2) где -неизвестная функция -неизвестные параметры. Задача состоит в том, чтобы определить далее значения этих параметров, при которых эмпирическая формула даёт хорошее приближение данной функцией, значения которой в точки равны (i=0,1,2…n). Разность между этими значениями обозначим через

i=0,1,2…n (3)


Задачи нахождения наилучших значений параметров сводится к некоторой минимизацией отклонений существует несколько способов решений этой задачи.


^

Метод наименьших квадратов



Запишем сумму квадратов отклонений (3) для всех точек :

(4)


Параметры эмпирической формулы (2) будем находить из условий min функции .В этом состоит метод наименьших квадратов.


Поскольку здесь параметры выступают в роли независимых функций S, то её min найдём приравнивая к нулю частные производные по этим переменным:

(5)

Полученные соотношения – системы управления для определения

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

(6)


Формула (4) для определения суммы квадратов отклонений S примет вид

(7)

Для составления системы уравнений (5) найдем частные производные функции S=S()

или


Решая последнюю систему относительно и получим многочлен (6)

Систему (9) можно записать в более компактном виде


где (m)
^



Лекция 17

Пример: метод наименьших квадратов для вывода эмпирической формулы, заданной в табличном виде:



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

x

0,75

1,50

2,25

3,00

3,75

y

2,50

1,20

1,12

2,25

4,28

Найти зависимость y=f(x)

Решение

Если изобразить табличные значения на графике (1) то легко убедиться, что в качестве эмпирической формулы для аппроксимации функции y=f(x) можно принять параболу, т.е.

квадратный трёхчлен


В данном случае m=2 n=4 и система (10) пример вид


Коэффициенты этой системы могут быть вычислены по формулам (11) i=0,1,2,3,4


Система уравнений (12) запишем в виде


Отсюда находим параметры таким образом (13)

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
















0,75

1,50

2,25

3,00

3,75

2,66

1,12

0,92

2,06

4,54

2,50

1,20

1,12

2,25

4,28

0,16

-0,08

-0,20

-0,19

0,26

0,064

-0,067

-0,179

-0,084

0,061



Пример Пусть на основании эксперимента получим значения функции y=f(x), которые записаны в таблицу

x

0,5

1,0

1,5

2,0

2,5

3,0

y

0,31

0,82

1,29

1,85

2,51

3,02



С помощью метода наименьших квадратов функцию y=f(x) аппроксимировать линейной функцией


Решение Составим систему для определения и


^

Предварительное вычисления



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


Искомый многочлен y=1,09x-0,28


Лекция 18




Задачи на собственные значения

Основные понятия


Большое число научно-технических задач, а также некоторые исследования в области вычислительной математики требует нахождения собственных значений и собственных векторов матриц.

Введем некоторые определения для изложения материала данного параграфа.

Рассмотрим квадратную матрицу n-го порядка.


Рассмотрим систему Ax=hx (1)



Когда система (1) имеет не нулевое решение (1)

тогда (2)

или

=0 (2)


Выражение (2) называется характеристическим или весовым полиномом относительно h


Корни этого многочлена являются собственными значениями матрицы А.

Они характеризуются тем свойством, что дают нетривиальные решение системы(1) . Чтобы было нетривиальное решение необходимо и достаточно (2) Действительно, если вместо стоит один из корней собственного полинома , то выражение (2) обращается в 0. И для этого существует ненулевое решение системы (1). Это решение и является собственным вектором. Поиск собственных значений и собственных векторов матрицы A является основной задачей теории устойчивости, надежности и т.п. Существует много методов нахождения собственных векторов и собственных значений матрицы А.

Рассмотрим некоторые из них.

Пример


Вычислить собственные числа и собственные векторы матрицы


Решение. Составим характеристический многочлен


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


Или запишем в виде системы уравнений


Эти уравнения линей зависимы (даже совпадают) поэтому оставим одно из них.

Полагаем и собственный вектор соответствующий числу имеет вид или,, где и единичные орты выбранной системы координат.

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


Отсюда


Вектор нормирован, нормируемый вектор , разделив его компоненты на наибольшую из них получим

Можно даже привести векторы к единичной длине разделив его компоненты на значения модулей векторов.

В этом случае

^

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




Пусть имеется характеристический определитель или


Корни этого полинома является собственными значениями матрицы А, причем пусть

(1)

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

,где - постоянные коэффициенты

Проведя преобразование А над вектором получим




Отсюда, т.к. вектор собственный вектор преобразования А, т.е. получим

AУ- называется итерацией вектора Последовательно образуя итерации , получим (2) (м-итераций)


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

Пусть

Координаты вектора в выбранном базисе .

Разлагая собственные векторы по векторам выбранного базиса получим

Отсюда подставляя (3) в (2) получим (3)


Или меняя порядок суммирования получим (4)


Но (4а)

Приравнивая (4) и (4а) получим

(5)

(6)


Разделив (6) на (5) получим


Пусть и , тогда


с учётом неравенства (1)


Литература.


  1. Волков Е.А. Численные методы.

  2. Турчак Л.И. Основы числительных методов.

  3. Демидович Б.И. и Марон И.А. Основы вычислительной математики.

  4. Копченова И.В. и Марон И.А. Вычислительная математика в примерах и задачах.

  5. Перумов У.Г. Числительные методы

Высшее образование Москва 2004г.


^



Содержание


 5

Лекция 1 5

Введение. Численные методы и приближённые вычисления 5

Методы решения 6

Абсолютная и относительная погрешность. 6

Погрешность арифметической операции 6

Лекция 2 7

Общие понятия об интерполировании. 7

Линейная интерполяция. 8

Интерполяционный многочлен Лагранжа. 8

Оценка погрешности интерполяционной формулы Лагранжа 9

Исследование остаточного члена при равноотстоящих узлах. 10

Лекция 3 10

Методы приближенного интегрирования. 10

Формулы Ньютона –Котеса. 10

Частные случаи. 11

Лекция 4 11

Численное дифференцирование. 12

Метод неопределенных коэффициентов. 13

Лекция 5 13

Разделённые разности 13

Интерполяционный полином Ньютона для неравно отстоящих значений аргумента 16

Конечные разности. 17

Связь конечных разностей и разделенных разностей. 17

Интерполяционный полином Ньютона для равноотстоящих значений аргумента. 18

Лекция 6 18

Классификация уравнений. Этапы численного решения. 18

Отделение корней. 19

Метод половинного деления (бисекций). 19

Метод итераций. 20

 22

Лекция 7 22

Метод ньютона (касательных). 22

Численные решения СЛАУ. 23

Метод Гаусса. 23

Лекция 8 25

Метод прогонки. 25

Лекция 9 28

Метод конечных разностей решение краевых задач ОДУ. 28

Лекция 10 29

Сплайны. 29

Кубический сплайн. 29

Лекция 11 30

Абсолютная величина и норма матрицы. 30

Метод простой итерации. 31

Оценка погрешности метода простой итерации. 31

Лекция 12 32

Приведение систем к виду, допускающему применение метода простых итераций. 32

Метод Зейделя. 33

Лекция 13 34

Методом Зейделя решить систему 34

Обусловленность систем линейных уравнений число обусловленности. 34

Лекция 14 36

Численные методы решения задачи Коши для ОДУ. 36

Метод последовательного дифференцирования. 36

Метод Эйлера 37

Лекция 15 37

Метод Рунге - Кутта 37

 39

Лекция 16 40

Эмпирические формулы 40

Метод наименьших квадратов 40

 42

Лекция 17 43

Пример: метод наименьших квадратов для вывода эмпирической формулы, заданной в табличном виде: 43

Предварительное вычисления 44

Лекция 18 44

Задачи на собственные значения 44

Основные понятия 44

Пример 45

Нахождение наибольшего по модулю собственного значения матрицы А. 46

 48

Содержание 49



Скачать файл (1133.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru