9982

Численный анализ ИП в частотной области

Реферат

Информатика, кибернетика и программирование

Численный анализ ИП в частотной области. Как указывалось ранее при моделировании ИП в частотной области обычно используется численный спектральный подход. Наибольшие преимущества такой подход обеспечивает при моделировании линейных устройств. В связи с этим при вычи

Русский

2013-03-19

92.5 KB

1 чел.

Численный анализ ИП в частотной области.

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

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

АХ =В, или

где: X - вектор неизвестных переменных, В – вектор местных констант, А - квадратная матрица с элементами ( - номер строки, - номер   столбца).

Формально эту систему можно решить, обратив матрицу А:

Х= А-1В

Рисунок 1. Классификация методов решения системы линейных  уравнений

Решение систем линейных уравнений производится прямыми или итерационными методами (рис. 1).

Прямыми методами называют такие методы, которые позволяют за конечное число действий получить точное решение системы. Термин «точное решение» следует понимать условно как характеристику алгоритма, а не реального вычислительного процесса. Алгоритмы, лежащие в основе прямых метод дают точное решение, если все величины в системе заданы все вычисления проводятся абсолютно точно, без ошибок округления. К прямым методам относятся правило Крамера, методы Гаусса, Жордана и LU-разложения в различных модификациях.

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

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

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

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

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

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

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

                 Ах= В                                             (1)

с квадратной невырожденной матрицей А, необходимо предварительно преобразовать эту систему к виду

                             х = Вх + с.                                             (2)

Здесь В — квадратная матрица с элементами bij (i, j = 1, 2, ..., m), с — вектор-столбец с элементами ci{ (г = 1, 2, ..., m).

В развернутой форме записи система (2) имеет следующий вид:

………………………………………………….……….

                                                                       (3)

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы (1) выразим неизвестное х1:

из второго уравнения - неизвестное х2-

и т д. В результате получим систему

......................................................................

                   (4)

в которой на главной диагонали матрицы  В находятся нулевые элементы. Остальные элементы выражаются по формулам

                                                                                (5)

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

Часто систему (1) преобразуют к виду х = х - r(Ах – b), где r - специально выбираемый числовой параметр.

2. Описание метода. Выберем начальное приближение x(0)=( x(0)1 x(0)2x(0)m)т. Подставляя его в правую часть системы (6.2) и вычисляя полученное выражение, находим первое приближение

х(1) = Bx(0) + с.

Подставляя приближение x(0) в правую часть системы (6.2), получим

х(2) = Bx(1) + с.

Продолжая этот процесс далее, получим последовательность х(0) х(1) …х(n)  

приближений, вычисляемых по формуле

                                                        (6)

В развернутой форме записи формула (6) выглядит так:

………………………………………….

                                               (7)

В случае, когда для итераций используется система (4) с коэффициентами, вычисленными по формулам (5), метод простой итерации принято называть методом Якоби.

Сходимость метода простой итерации.

Теорема. Пусть выполнено условие (8)

Тогда: 1) решение х системы (2) существует и единственно, 2) при произвольном начальном приближении x(0)   метод простой итерации сходится и справедлива оценка погрешности

Замечание 1. Теорема дает простое достаточное условие (8) сходимости метода простой итерации. Грубо это условие можно интерпретировать как условие достаточной малости элементов b матрицы В в системе, приведенной к виду (2).

Замечание   2. Если , то условие (8) принимает вид  

Для метода Якоби это условие в силу равенств bii = 0, bij = - aij /а* эквивалентно условию диагонального преобладания. Если же воспользоваться условием (8) при, то для метода Якоби получим другое условие диагонального преобладания:

                                                  (9)

4. Апостериорная оценка погрешности.

Предложение 6.1.  Если выполнено условие (8), то справедлива апостериорная оценка погрешности

                                                    (10)

Запишем равенство при k = п - 1 в виде

Тогда

Для завершения доказательства достаточно заметить, что полученное неравенство эквивалентно неравенству (10).

Замечание. Величину, стоящую в правой части неравенства (10), можно легко вычислить после нахождения очередного приближения х(n).

Если требуется найти решение с точностью e, то в силу (10) следует вести итерации до выполнения неравенства

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

                                              (11)

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

                                                            (12)

Отметим, что для метода простой итерации его применение обосновано только тогда, когда  в этом случае  и выполнение неравенства (12) влечет за собой выполнение неравенства (11). Однако в большинстве реальных случаев величина оказывается близкой к единице и поэтому. В этих случаях e1< e и использование критерия (12) приводит к существенно преждевременному окончанию итераций. Величина здесь оказывается малой не потому, что приближения х(п-1) и х(п) близки к решению, а потому, что метод сходится медленно.

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

1. Описание метода. Пусть система (1) приведена к виду (4) с коэффициентами, вычисленными по формулам (5).

Метод Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что при вычислении очередного (k + 1)-го приближения к неизвестному xi при i > 1 используют уже найденные (k + 1)-е приближения к неизвестным, a не приближения, как методе Якоби.

На (k + 1)-й итерации компоненты приближения x(k+1) вычисляются по формулам

………………………………………….

                                                                         (13)

Введем нижнюю и верхнюю треугольные матрицы

,  

Тогда расчетные формулы метода примут компактный вид:

                                        (14)

Заметим, что В = В1 + В2 и поэтому решение х исходной системы удовлетворяет равенству

                                                 (15)

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.

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

Теорема 6.3.    Пусть

где - одна из норм

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

3. Апостериорная оценка погрешности.

Предложение. Если выполнено условие  то для метода Зейделя справедлива апостериорная оценка погрешности

                                                      (16)

Положим k = п - 1 и запишем равенство (6.28) в следующем виде:

Тогда

откуда и следует неравенство (16).

Полученное неравенство позволяет сформулировать простой критерий окончания итерационного процесса. Если требуется найти решение с точностью e > 0, то итерации метода Зейделя следует вести до выполнения неравенства или эквивалентного ему неравенства

                             ,                                       (17)

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

Приведем геометрическую интерпретацию метода Зейделя в случае m = 2, т.е. в случае решения системы

Первое уравнение задает на плоскости х1Ох2 прямую l1 второе - прямую l2 (рис. 2). Расчетные формулы метода принимают вид

где 

Рис. 2.

Пусть приближение х(k)  уже найдено. Тогда при определении х(k+1) координата х2= x2(k)  фиксируется и точка x перемещается параллельно оси  Ох1 до пересечения с прямой  l1. Координата х1 точки пересечения принимается за х1(k+1). Затем точка х перемещается вдоль прямой х1 = х1(k+1). до пересечения с прямой l2. Координата х2 Точки пересечения принимается за х1(k+1).

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


EMBED Equation.3


 

А также другие работы, которые могут Вас заинтересовать

52539. Всі ми родом із дитинства 97 KB
  Евеліна Хромченко Дитинство Дитинствоказка мов чарівна мить Там завжди сонячно і світло. Надія Красоткіна Дитинство це коли день починається з першим променем сонця звуком тихих маминих кроків запахом теплого хліба співом птахів і триває довгодовго це коли дерева великі а ти внизу і помічаєш так багато: і мурашки і бджолу на квітці і пухнасту гусеницю і чуєш як росте трава і можеш залізти на найвище дерево і переплести саму широку річку і все можеш зробити сам. Варто подумати про дитинство і память підкине дивні...
52540. Свято здоровя 43 KB
  Підвищувати відповідальність за особисте здоровя, здоровя родини; пропагувати і заохочувати до співпраці дітей та батьків; розвивати і зміцнювати в учнів почуття прекрасного в побуті, працьовитість, повагу до звичаїв і традицій рідного народу; виховувати повагу в особистих стосунках, почуття колективізму та взаємодопомоги.
52541. Сценарій свята для учнів 2-х класів «Різдвяне диво» 81 KB
  Заходять колядники звіздар ангел зірка коза дохтур Звіздар. Де коза ходить там жито родить Де коза ногою там жито копою Де коза рогом там жито стогом. Коза скаче а потім падає Пуць Коза впала нежива стала Ой Ой Яка добра тваринка була Що ж то робити Усі. Де тут хто тут пацієнт Виліковую в момент Робить козі укол коза оживає встає танцює танець всі плескають у долоні Усі.
52542. Ти наше диво калинове, кохана українська мово 61 KB
  Ведуча Мова А що таке мова Народ говорить слово до слова зложиться мова а Т . Ведучий Найбільше і найдорожче добро кожного народу це його мова ота жива схованка людського духу його багата скарбниця в яку народ складає і своє давнє життя і свої сподіванки розум досвід почуття. Добута з надр далеких поколінь Ти скарб наш вічний українська мова. Мова ...
52543. ДИВОСВІТ. Методичні рекомендації 8.27 MB
  Методичні рекомендації «Дивосвіт» вихователя Менського дошкільного закладу «Сонечко» Шевель Наталії Володимирівни допоможуть педагогічним працівникам дошкільних закладів у створенні та облаштуванні розвивального простору в групах дошкільних навчальних закладів.
52544. Методичний проект «Центр дитячої творчості Дивосвіт як заклад життєвої компетентності» 58.5 KB
  Підвищити рівень орієнтованності навчально виховного процесу закладу на розвиток життєвої компетентності особистості учня. Націлити педагогів закладу до розробки та впровадження авторських програм навчальних посібників нового покоління 3. Переорієтнувати виховну систему закладу відповідно до вимог часуформування через освіту здорового способу життя дітей та молоді інтеграцію освіти до європейського та світового освітнього простору 5.
52545. Україно! Мій духмяний дивоцвіт 53 KB
  Разом: Збулося Хлопчик: 24 серпня 1991 року Верховна Рада України урочисто прийняла Акт проголошення України незалежною самостійною демократичною державою. На цьому шляху загинула незліченна кількість кращих синів і дочок України які відстоювали її незалежність. Шлях України позначений високими степовими могилами руїнами та прекрасними безіменними невідомо коли і ким складеними піснями. Хлопчик: Народе України Твоєю силою волею.
52546. Внутрішні гіперпосилання на веб-сторінках 107.5 KB
  Ввести поняття внутрішнього посилання, ознайомити з правилом запису внутрішнього посилання, навчити учнів створювати внутрішні гіперпосилання на веб-сторінці, розвивати пізнавальну активність, вміння індивідуально працювати за комп’ютером, виховувати інтерес до інформатики і біології, формувати інтерес учнів до природи рідного краю і питань збереження рослин.
52547. Усі уроки української літератури в 5 класі 25.52 MB
  Навчальний посібник містить конспекти усіх уроків української літератури для 5 класу 12-річної школи. Серед них уроки текстуального вивчення творів, уроки позакласного читання, розвитку звязного мовлення, виразного читання, літератури рідного краю, тематичного оцінювання. Запропоновані розробки містять елементи нестандартних підходів, інтерактивних методик. Даний посібник розрахований на вчителів української літератури шкіл різних типів, керівників методичних, викладачів та студентів вищих навчальних закладів.