Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Вычислительная сложность метода Холесского






В общем случае перестановки при решении СЛАУ с разреженной матрицей определяются в процессе компромисса между требованиями устойчивости алгоритма (перестановки строк и столбцов матрицы СЛАУ в ходе выбора главного элемента в методе Гаусса) и желанием учета разреженности матрицы (желанием уменьшить заполнение матрицы в процессе исключения). Однако алгоритм Холесского для СЛАУ с симметричной положительно определенной матрицей не требует перестановок для поддержания устойчивости алгоритма (не требует выбора главного элемента). Матрицу СЛАУ в этом случае можно переупорядочить еще до начала реального численного разложения. Выбранная структура хранения матрицы при ее разложении остается статичной. Таким образом, три задачи

  1. Выбор надлежащего упорядочения СЛАУ;
  2. Формирование подходящей схемы хранения для матрицы СЛАУ (этот вопрос обсуждается в последующих лекциях)4
  3. Реальное вычисление

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

Теорема. Число операций, необходимых для вычисления треугольного множителя Холесского симметричной положительно определенной матрицы , равно

 

,

 

где - размер матрицы СЛАУ, - количество ненулевых элементов в аргументе, - i- ый столбец матрицы .

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал