Читать онлайн «Методы неполной факторизации для решения алгебраических систем»

В. П. ИЛЬИН Методы неполной факторизации для решения алгебраических систем ПРЕДИСЛОВИЕ Решение систем линейных алгебраических уравнений высокого порядка — классическая задача вычислительной математики, сохраняющая свою актуальность на любом уровне развития компьютерных технологий. Особое место здесь занимают проблемы с разреженными матрицами специальной структуры, возникающими из сеточных аппроксимаций многомерных краевых задач и предъявляющими особенно жесткие требования к быстродействию и оперативной памяти ЭВМ. За последние десятилетия для решения этих ресурсоемких задач наиболее эффективным средством стали итерационные методы неполной факторизации, применяемые совместно со спектральными или вариационными принципами ускорения сходимости последовательных приближений. Их главными достоинствами являются рекордная практическая экономичность, высокие теоретические оценки скорости сходимости итераций и широкие возможности конструирования адаптивных алгоритмов для разных классов задач. У методов неполной факторизации своя интересная судьба. Они были открыты в 50-е годы известным специалистом по вычислительной гидродинамике Николаем Ивановичем Булеевым (1922-1984 гг. ), работавшим в Физико-энергетическом институте, г. Обнинск. В математическом отделе ФЭИ, которым я тогда руководил, эти алгоритмы прошли тщательную апробацию и обнаружили очень хорошие качества. Однако так случилось, что после опубликования методы неполной факторизации еще не привлекли пристального внимания отечественных специалистов. Этому было две причины. Во-первых, полученные тогда результаты содержали в основном данные экспериментальных расчетов, без должного теоретического обоснования и оценок. Во-вторых, в то время активно развивались исследования по теории последовательной верхней релаксации и методов переменных направлений, получивших широкое распространение. В последующие годы методы неполной факторизации неоднократно переоткрывались зарубежными учеными и получили дальнейшее развитие в работах X. Ван дер Ворста, Р. Боувенса, О. Аксельсо- на, В. П. Ильина и многих других авторов. Они стимулировали новые исследования и привнесли ряд интересных результатов в теорию матриц. К настоящему времени методы неполной факторизации пока не получили должного освещения в учебной и монографической литературе. Предлагаемая книга В. П/Ильина является первым систематическим изложением современных результатов в данной области. Мы надеемся, что она вызовет интерес у специалистов по вычислительной математике и решению прикладных задач, а также будет несомненно полезна аспирантам и студентам. Академик РАН Г. И. Марчук Посвящается памяти первооткрывателя методов неполной факторизации Николая Ивановича Булеева ВВЕДЕНИЕ Задача решения линейных алгебраических уравнений Au = f (0. 1) с известными вещественными элементами вектора / = {/,} и квадратной невырожденной матрицей А = {а,^} (i,j = 1,... , JV) — одна из фундаментальнейших в вычислительной математике.