روش های تکراری برای حل معادله های خطی بزرگ روش های بیش تر

مقدمه

بیش تر مسائل لازم است که از طریق معادله های خطی بزرگ Ax = b در ماتریس A حل شوند، که خوشبختانه کم هستند. این چنین قواعدی برای مثال در کاربرد معادله های تفاصل یا معادله های مبانی محدود بوجود می آید تا به طور تقریبی مسائل ارزش حدودی را در معادله های تفاضل نسبی حل کنند. معادله های حذفی که در فصل ۴ بود اینجا قابل استفاده نیست، زیرا که بدون محدودیتهای در آنها تمایل دارند به تکوین بیش تر یا ماتریسهای رابط فشرده، برای ایجاد تعدادی از عملیات محاسباتی لازم برای حل معادلات بسیار بزرگ، حتی در کامپیوترهای لعروزی، از حقیقتی که ماتریسهای رابط دیگر در حافظه ی کامیپوتر موجود نصب نشده اند.

به همین دلایل، محققان از مدتها قبل به روشهای تکراری برای حل معادلات خطی روی آوردند. در این روش ها ابتدا با بردار اولیه (x1، یک مجموعه ی متوالی از بردارها بوجود می آید

x⁽⁰⁾ -> x⁽¹⁾ -> x⁽²⁾ ->… که به سمت جواب x گرایش دارد. ویژگی مشترک این روشها این است که مرحله ی تکرار فردی

x ⁽ⁱ⁾ -> x⁽ⁱ⁺¹⁾ به تعدادی عملیات نیاز دارد که با ضرب A با یک بردار قابل مقایسه است ـ یک مقدار بسیار کم در صورتیکه مقدار A هم بسیار کم است. به همین دلیل می توان با تعدادی عملیات مناسبت، تعداد زیادی از تکرارهای محاسبه کرد.

لازم به ذکر است که بدون هیچ دلیل دیگری از اینکه این روشها فقط معادلات خطی راست حل می شوند. روشهای تکراری زیر مجموعه ی روشهای حذف هستند در صورتیکه A یک ماتریس کوچک (در اینجا ماتریس ۱۰۰×۱۰۰ کوچک است) یا اینکه یک ماتریس کم نیست.

تا حدودی خارج از این چارچوب روش معروفی است از اصلاح تکراری (که در قسمت ۸۰۱۰۹ و ۸۰۱۰۱۱ می بینیم) و روش گرادیان فردوج (که در بخش ۸۰۷ می بینیم). اصلاح تکراری تقریباً به کرّات استفاده شده است و کارکرده است تا مکرراً اصلاح کند صحت جواب تقریبی x را از دستگاه معادلاتی که بوسیله ی روش حذفی در محاسبه ی ماشینی به دست آمده است. ویژگی های کلی روشهای تکراری که در بالا ذکر شده استف اغلب در روش گرادیان مزدوج نیز استفاده می شود با این تفاوت که راه و روش حساب با محاسبه ی دقیق x با تعداد محدودی از مراحل پایان می پذیرد. با توجه به کاربرد روش گرادیان فردوج همین نکته ها برای روشهای تکراری دقیق نیز قابل استفاده است. به همین دلیل ما در مورد این روش در همین فصل بحث کرده ایم.

علاوه بر اینکه برای حل سیستم های خاص و مهم معادلات روشهای مستقیمی وجود دارد که در یک تعداد محدودی از مراحل بوجود آمده است که برای روشهای تکراری خوب است: یکی از نخستین این مراحل الگریستم با نمن هست که در بخش ۸۰۸ توضیح داده شده است.

باید یادآورشد که اخیراً یک تعداد تکنیکهای کلی تکمیلی برای بررسی کردن سیستم های بزرگ معادلات Ax = b با A تنها ماتریکس محدود توسعه داده شده است. چنین روشهای خودشان را با روشهای مناسب ذخیره سازی چنین ماتریسهایی مرتبط می سازد و با تعیین ماتریسهای تبدیل مناسب P₂ , P₁ که در کاربرد روشهای حذف سیستم های معادل

y = P^-1₂ x و P₁ AP₂y = P₁ b ماتریسهایی میانی حاصل هر چند ناچیز باقی می مانند. یکی از این روشها در بخش ۴٫A شرح داده شده است. برای توضیح مناسب ما خواننده را به آوردن و ذکر کردن ادبیات در اینجا ارجاع داده ایم.

تفسیر مشروح روشهای تکراری را می توان در کتاب وارگاو یانگ پیدا کرد.

۸۰۱ روشهای کلی ترسیم روشهای تکراری.

فرض کنیم تنها ماتریکس A غیر مفرد n×n و یک سیستم از معادله های خطی داده شده است.

Ax = b (۸۰۱۰۱)

با حل دقیق A-1 b = x ما روشهای تکراری از شکل (معادله ی الف) را با کمک یک ماتریکس B غیر مفرد n×n چنین الگوریستم های تکراری را می توان از طریق (معادله ی ب) محاسبه کرد،

با گذاشتن (معادله ی ج)

یا حل کردن x(i+1) معادله د ۴٫ ۷٫ ۸

در کل چنین روشهای تکراری ابتدا توسط ویتمپر مورد توجه قرار گرفت. یاد آورد شد که ۴٫ ۷٫ ۸ با تکرار بردار خاص بعد یکسان است: (بردار۹)

جایی که ماتریس W در مرتبه ی (n +1)، با مقدار خاص ho = 1 مطابقت دارد، دارای بردار مشخصه ی چپ (۱۶۰) و بردار مشخصه ی راست چپ (۱۶۰) و بردار مشخصه ی راست [۱x] که x = A-1 b بر اساس نتایج بدست آمده از بخش ۳٫ ۶٫ ۶ دنباله ی [۱x(i)] با [۱x] همگرا خواهد بود فقط اگر ho = 1 باشد مقدار ویژه مسلط ساده ای است از ماتریس w براتی مثال، اگر

h_o = 1>/h₁/>…> /h_n/,

باقی مانده ی مقدار ویژه ی h₁…h_n از ماتریس w (آنها مقدار ویژه های I – B^-1 Aهستند) در قدر مطلق از یک کوچکتر از هر تابع از ماتریس غیر مفرد B به یک روش تکراری بالقوه منتهی می شود (۴٫ ۱٫ ۸) ماتریکس B بزرگتر شروط زیرا برای استفاده بیش تر روش صدق می کند

۱ـ سیستم معادلات ۳٫ ۱٫ ۸ براحتی برای ^{i +1)}⁾x حل می شود.

۲ـ معادلات I – B^-1 A واحدهایی کوچکی دارند.

ماتریس B با A مطابقت دارد، احتمالاً نوع اول درست خواهد بود این سؤالها از بهینگی و همگرایی در بخشهای بعدی تجزیه و تحلیل می شوند. در اینجا ما فقط تعدادی روشهای تکراری خاصی (۳٫ ۱٫ ۸) را نشان می دهیم که بوسیله ی تابعهای گوناگون B بدست می آید. به همین منظور ما تجزیه ی استاندارد تابع A را ارائه می دهیم. (معادله ی خ)

بلکه علائم اختصاری (معادله ج)

با در نظر گرفتن a_ii = o برای معادله ی i = 1, 2, …, n

(۱) در روش ژاکوبی یا روش مرحله ی کلی (توتال است) انتخاب یکی از آنها (۷٫ ۱٫ ۸)

B = D , I-B^-1 A= j

عدد یک اینگونه از معادله ی (۳٫ ۱٫ ۸) نظریه ی تکرار بدست می آید (معادله ی م)

(۲) در نظریه ی گاوس سیدل یا نظریه ی گامهای منفرد (سینگل راستب) انتخاب یکی از این روشها ۸٫ ۱٫ ۸

عدد یک اینگونه برای (۳٫ ۱٫ ۸) بدست آمده است.

(۳) روش اصلاح تکرار در نوع خودش یک مورد خاصی است. اینجا موقعیت زیر در نظر گرفته شده است. وقتیکه جواب روشی حذفی برای حل معادله ی Ax = b یک می شود، به دلیل خطاهای ناشی از گردکردن، یک جواب تقریبی خوب معادله x⁽⁰⁾ برای حل دقیق x و یک ماتریس مثلثی L و R بالاتر و پایین تر به ترتیب مثل A = LR جواب تقریبی x⁽⁰⁾ می تواند توسط میانگین روش تکرار شکل ۳٫ ۱٫ ۸ که انتخاب شده است بهتر شود.

B = LR

(۳٫ ۱٫ ۸) مساوی است با

B ( x⁽ⁱ⁺¹⁾ – x⁽ⁱ⁾ ) = r ⁽ⁱ⁾

با باقیمانده r ⁽ⁱ⁾ = b – Ax⁽ⁱ⁾

از معادله (۹٫ ۱٫ ۸) بدست می آید که

u⁽ⁱ⁾ = R^-1 L^-1 r⁽ⁱ⁾ x⁽ⁱ⁺¹⁾= x⁽ⁱ⁾ + u⁽ⁱ⁾ (۱۵٫ ۱٫ ۸)

لازم به ذکر است که u(i) می تواند بوسیله ی حل سیستم های معادلات مثلثی به راحتی حل شود.

Ru⁽ⁱ⁾ = 7 I_z = r⁽ⁱ⁾ (۱۱٫ ۱٫ ۸)

در کل (اگر A عینی به حالت نیست) روال کار بسیار سریع به هم می پیوندند. تا بحال x² , x¹ با جواب دقیق x مطابق است تا با دستگاه درست ساخته شود از آنجای که این دلیل تابع صحیح بسیار مهم است که محاسبه ی r⁽ⁱ⁾ در دقت مضافعی انجام شود. بعد از محاسبه ی

X⁽ⁱ⁺¹⁾=x⁽ⁱ⁾ + u⁽ⁱ⁾, Z از معادله ی (۱۱٫ ۱٫ ۸) و (۱۰٫ ۱٫ ۸) نیازی به وقت بی شمار وجود ندارد [برنامه ها و مثالهای عددی بهبود تکرار را می توان در کتابهای ویکینسون وو رینچ و فورسیس و مولد پیدا کرد]