حل عددی سیستم های معادلات جبری خطی. شرایط کافی برای همگرایی یک فرآیند تکراری

سخنرانی روش های تکراری برای حل یک سیستم معادلات خطی جبری.

شرایط همگرایی فرآیند تکراری روش ژاکوبی روش سیدل

روش تکرار ساده

یک سیستم خطی معادلات جبری

برای اعمال روش های تکراری، سیستم باید به شکلی معادل کاهش یابد

سپس تقریب اولیه برای حل سیستم معادلات انتخاب شده و دنباله ای از تقریب به ریشه پیدا می شود.

برای همگرا شدن فرآیند تکراری، کافی است که شرط
(هنجار ماتریس). معیار خاتمه برای تکرارها به روش تکراری اعمال شده بستگی دارد.

روش ژاکوبی .

ساده ترین راه برای آوردن سیستم به فرمی مناسب برای تکرار به شرح زیر است:

از معادله اول سیستم مجهول را بیان می کنیم ایکس 1، از معادله دوم سیستمی که بیان می کنیم ایکس 2 و غیره

در نتیجه، سیستمی از معادلات را با ماتریس B بدست می آوریم که در آن صفر عناصر روی قطر اصلی قرار دارند و عناصر باقیمانده با فرمول های زیر محاسبه می شوند:

اجزای بردار d با فرمول های زیر محاسبه می شوند:

فرمول محاسبه روش تکرار ساده به صورت زیر است:

یا در نماد مختصات به شکل زیر است:

معیار خاتمه تکرارها در روش ژاکوبی به شکل زیر است:

اگر یک
، می توان معیار ساده تری برای پایان دادن به تکرارها اعمال کرد

مثال 1حل سیستم معادلات خطی به روش ژاکوبی.

اجازه دهید سیستم معادلات داده شود:

باید راه حلی برای سیستم با دقت پیدا کرد

ما سیستم را به شکلی مناسب برای تکرار می آوریم:

ما یک تقریب اولیه را انتخاب می کنیم، به عنوان مثال،

بردار سمت راست است.

سپس اولین تکرار به صورت زیر است:

تقریب های زیر برای حل به طور مشابه به دست آمده است.

هنجار ماتریس B را پیدا کنید.

ما از هنجار استفاده خواهیم کرد

از آنجایی که مجموع ماژول های عناصر در هر ردیف 0.2 است، پس
، بنابراین ملاک ختم تکرارها در این مشکل است

اجازه دهید هنجارهای تفاوت بردارها را محاسبه کنیم:

زیرا
دقت مشخص شده در تکرار چهارم به دست می آید.

پاسخ: ایکس 1 = 1.102, ایکس 2 = 0.991, ایکس 3 = 1.0 1 1

روش سیدل .

این روش را می توان اصلاح روش ژاکوبی در نظر گرفت. ایده اصلی این است که هنگام محاسبه بعدی (n+1)-ام تقریب به مجهول ایکس مندر i> 1استفاده از قبلا پیدا شده است (n+1)-نزدیک شدن به ناشناخته ایکس 1 ,ایکس 2 , ...,ایکسمن - 1، نه nتقریب، مانند روش ژاکوبی.

فرمول محاسبه روش در نماد مختصات به صورت زیر است:

شرایط همگرایی و معیار خاتمه برای تکرارها را می توان مانند روش ژاکوبی در نظر گرفت.

مثال 2حل سیستم معادلات خطی به روش سیدل.

حل 3 سیستم معادله را به طور موازی در نظر بگیرید:

ما سیستم ها را به شکلی مناسب برای تکرار می آوریم:

توجه داشته باشید که شرط همگرایی
فقط برای سیستم اول انجام شد. ما در هر مورد 3 تقریب اولیه برای حل را محاسبه می کنیم.

سیستم اول:

راه حل دقیق مقادیر زیر خواهد بود: ایکس 1 = 1.4, ایکس 2 = 0.2 . فرآیند تکراری همگرا می شود.

سیستم دوم:

مشاهده می شود که فرآیند تکراری واگرا می شود.

راه حل دقیق ایکس 1 = 1, ایکس 2 = 0.2 .

سیستم سوم:

مشاهده می شود که فرآیند تکراری حلقه زده است.

راه حل دقیق ایکس 1 = 1, ایکس 2 = 2 .

بگذارید ماتریس سیستم معادلات A متقارن و مثبت معین باشد. سپس برای هر انتخابی از تقریب اولیه، روش سیدل همگرا می شود. شرایط اضافی در مورد کوچک بودن هنجار برخی از ماتریس ها در اینجا اعمال نمی شود.

روش تکرار ساده.

اگر A یک ماتریس قطعی متقارن و مثبت باشد، سیستم معادلات اغلب به شکل معادل کاهش می یابد:

ایکس=ایکس-τ(A ایکس- ب)، τ یک پارامتر تکراری است.

فرمول محاسبه روش تکرار ساده در این مورد به صورت زیر است:

ایکس (n+1) =ایکس n- τ (A ایکس (n) - ب).

و پارامتر τ > 0 طوری انتخاب می شود که در صورت امکان حداقل مقدار را داشته باشد

بگذارید λ min و λ max حداقل و حداکثر باشند مقادیر ویژهماتریس A. انتخاب بهینه پارامتر است

در این مورد
حداقل مقدار را برابر با:

مثال 3 راه حل سیستمی معادلات خطیروش تکرار ساده (در MathCAD)

اجازه دهید سیستم معادلات Ax = b

برای ساختن یک فرآیند تکرار شونده، پیدا می کنیم مقادیر ویژهماتریس های A:

- از یک تابع داخلی برای یافتن مقادیر ویژه استفاده می کند.

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

شرط همگرایی برآورده می شود.

بیایید تقریب اولیه - بردار x0 را در نظر بگیریم، دقت را روی 0.001 قرار دهیم و با استفاده از برنامه زیر، تقریب اولیه را پیدا کنیم:

راه حل دقیق

اظهار نظر. اگر برنامه ماتریس rez را برگرداند، می توانید تمام تکرارهای یافت شده را مشاهده کنید.

1. بگذارید قسمتی شناخته شود که حاوی یک ریشه از معادله f(x) = 0 باشد. در صورت وجود این شرایط می توان از روش تکرار ساده استفاده کرد.

2. بر اساس تابع f(x)، یک تابع j(x) ساخته می شود که سه شرط را برآورده می کند: باید به طور پیوسته قابل تفکیک باشد (j(x)нC 1)، به طوری که معادله x = j(x) معادل معادله f(x)=0 است. همچنین باید بخش ترجمه به خودت.

خواهیم گفت که تابع j (ایکس ) بخش [آ , ب ] به خود اگر برای هرایکس Î [ آ , ب ], y = j (ایکس ) نیز متعلق است[ آ , ب ] ( y Î [ آ , ب ]).

شرط سوم بر روی تابع j(x) اعمال می شود:

فرمول روش: x n +1 = j (xn).

3. وقتی این سه شرط برآورده شد، برای هر تقریب اولیه x 0 دنباله ای از تکرارها x n +1 = j(xn) به ریشه معادله همگرا می شود: x = j(x) در قطعه ().

به عنوان یک قاعده، به عنوان x 0 یکی از انتهای انتخاب شده است.

,

که در آن e دقت مشخص شده است

عدد x n +1 به شرط توقف فرآیند تکرار شونده است مقدار تقریبی ریشه معادله f(x) = 0 در قطعه، با روش تکرار ساده با دقت یافت می شوده .

الگوریتمی برای اصلاح ریشه معادله بسازید: x 3 + 5x - 1 = 0 بر روی قطعه با تکرار ساده با دقت e .

1. تابع f(x) = x 3 + 5x-1 به طور پیوسته بر روی یک قطعه حاوی یک ریشه معادله قابل تمایز است.

2. بزرگترین مشکل در روش تکرار ساده، ساخت یک تابع j(x) است که تمام شرایط را برآورده می کند:

در نظر گرفتن: .

معادله x = j 1 (x) معادل معادله f(x) = 0 است، اما تابع j 1 (x) به طور پیوسته در بازه قابل تمایز نیست.

برنج. 2.4. نمودار تابع j 2 (x)

از سوی دیگر، بنابراین، . از این رو: تابعی است که به طور پیوسته قابل تمایز است. توجه داشته باشید که معادله x = j 2 (x) معادل معادله f(x) = 0 است. . از نمودار (شکل 2.4) می توان دید که تابع j 2 (x) قطعه را به خود ترجمه می کند.

شرطی که تابع j(x) قطعه را به خود تبدیل می کند را می توان به صورت زیر فرموله کرد: اجازه دهید دامنه تابع j(x) و دامنه j(x) باشد.

اگر پاره به قطعه تعلق داشته باشد، تابع j(x) قطعه را به خود می گیرد.

, .

تمام شرایط برای تابع j(x) برآورده می شود.

فرمول فرآیند تکراری: x n +1 = j 2 (xn).

3. تقریب اولیه: x 0 = 0.

4. شرط توقف فرآیند تکراری:

برنج. 2.5. حس هندسیروش تکرار ساده

.

وقتی این شرط برآورده شد، x n +1 – مقدار تقریبی ریشه روی قطعه, با تکرار ساده با دقت پیدا می شود ه. روی انجیر 2.5. کاربرد روش تکرار ساده نشان داده شده است.

قضیه همگرایی و برآورد خطا

اجازه دهید بخش شامل یک ریشه معادله است x = j (x)، عملکرد j(x ) به طور مداوم در بخش قابل تمایز است , بخش را ترجمه می کند به خود، و شرایط:

.

سپس برای هر گونه تقریب اولیه x 0 О دنباله به ریشه معادله همگرا می شود y = j(x ) در بخش و برآورد خطا:

.

پایداری روش تکرار ساده تحت شرایط قضیه همگرایی، الگوریتم روش تکرار ساده پایدار است.

پیچیدگی روش تکرار ساده. مقدار حافظه کامپیوتر مورد نیاز برای اجرای روش تکرار ساده ناچیز است. در هر مرحله باید x n را ذخیره کنید , x n +1 , q و ه.

اجازه دهید تعداد عملیات حسابی مورد نیاز برای اجرای روش تکرار ساده را تخمین بزنیم. اجازه دهید تخمینی برای عدد n 0 = n 0 (e) بنویسیم به طوری که برای همه n ³ n 0، نابرابری زیر برقرار باشد:

از این تخمین نتیجه می شود که هر چه q به وحدت نزدیکتر باشد، روش کندتر همگرا می شود.

اظهار نظر. وجود ندارد قانون کلیساختن j(x) از f(x) به گونه ای که تمام شرایط قضیه همگرایی برآورده شود. روش زیر اغلب استفاده می شود: تابع j به عنوان تابع j(x) = x + k × f(x) انتخاب می شود، که در آن k – مقدار ثابت.

هنگام برنامه نویسی یک روش تکرار ساده، توقف یک فرآیند تکرار شونده اغلب مستلزم دو شرط است که باید به طور همزمان برآورده شوند:

و .

تمام روش های تکراری دیگری که در نظر خواهیم گرفت، موارد خاصی از روش تکرار ساده هستند. مثلاً وقتی روش نیوتن یک مورد خاص از روش تکرار ساده است.

در این بخش، یک فرآیند تکرار ثابت را زمانی در نظر می گیریم که پارامتر ماتریس و تکرار باشد به شاخص بستگی ندارد ، و قضیه زیر را در مورد شرایط کافی برای همگرایی آن اثبات کنید.

قضیه سامارسکی

اجازه دهید یک ماتریس قطعی مثبت خود الحاق است:

,
,

یک ماتریس قطعی مثبت است، - عدد مثبت:

,
.

سپس برای هر انتخابی از تقریب صفر یک فرآیند تکراری که با فرمول بازگشتی تعریف می شود ، به حل سیستم اصلی همگرا می شود.

قبل از اینکه به اثبات قضیه بپردازیم، اجازه دهید با جزئیات بیشتر در مورد نیاز اصلی آن یعنی قطعیت مثبت ماتریس صحبت کنیم.
. این الزام را می توان به صورت زیر بازنویسی کرد:

,
,
.

به عنوان مثال، به طور خاص، فرض می کند که ماتریس مثبت قطعی است علاوه بر این، نابرابری فاصله زمانی را که پارامتر می تواند تغییر کند را تعیین می کند :

.

پس از این سخنان به اثبات قضیه می پردازیم. اجازه دهید از رابطه بیان کنیم از طریق :

و جایگزین فرمول تکرار شونده برای دنباله تکرار شونده. در نتیجه، دریافت می کنیم:

.

تفاوت بین فرمول تکراری و همگن بودن آن است.

ماتریس مثبت قطعی است بنابراین غیر منحط است و معکوس دارد
. با کمک او رابطه عودقابل حل است
:

، بنابراین
.

ضرب دو طرف برابری سمت چپ در ماتریس ، یک رابطه عود دیگر به دست می آوریم

.

دنباله ای از عملکردهای مثبت را در نظر بگیرید:

.

اجازه دهید یک عبارت مشابه برای
و با استفاده از فرمول های تکرارشونده و:

از خود الحاقی ماتریس و فرمول ها دنبال می شوند

در نتیجه فرمول به شکل زیر در می آید:

بنابراین، دنباله ای از توابع مشروط به شرط
یک دنباله یکنواخت بدون افزایش را تشکیل می دهد که از پایین با صفر محدود شده است

.

,

جایی که
یک ثابت کاملاً مثبت است. در نتیجه با توجه به و خواهیم داشت

از این نابرابری و همگرایی توالی تابع ها به دنبال آن است
در
. در نوبتش
، بنابراین

قضیه ثابت شده است.

1. روش تکرار ساده

این نام به روشی داده شد که در آن، به عنوان یک ماتریس ماتریس هویت انتخاب می شود:
، و پارامتر تکرار شونده فرض می شود مستقل از عدد تکرار است . به عبارت دیگر، روش تکرار ساده یک روش ثابت صریح در زمان تکرار بعدی است
با فرمول بازگشتی محاسبه می شود

فرض می کنیم که ماتریس شرط قضیه سامارسکی را برآورده می کند،
، سپس فرمولی که مرز فاصله همگرایی را با توجه به پارامتر تکراری تعیین می کند. ، شکل می گیرد

.

اجازه دهید
- مبنای متعارف بردارهای ویژه عملگر مربوط به ماتریس . با قطعیت مثبت، تمام مقادیر ویژه آن مثبت هستند. بیایید شماره آنها را به ترتیب نزولی در نظر بگیریم:

بیایید بردار را تجزیه کنیم
بر اساس بردارهای ویژه

در نتیجه، از فرمول نتیجه می شود که روش تکرار ساده برای هر یک همگرا می شود متعلق به فاصله

.

ما یک مطالعه بیشتر از روش تکرار ساده را بر روی یک تحلیل خاص از فرمول بازگشتی خواهیم ساخت. اجازه دهید ماتریس عملگر انتقال را معرفی کنیم

,

و فرمول را به صورت بازنویسی کنید

.

در عین حال، خطا
یک رابطه عود مشابه، فقط همگن را برآورده می کند

.

اجازه دهید دو لم را ثابت کنیم که به ما امکان می دهد شرایط همگرایی روش تکرار ساده را به طور کامل بررسی کنیم.

لم 1

اجازه دهید عملگری که ماتریس را تولید می کند ، دارای بردار ویژه است با ارزش ویژه ، سپس عملگر انتقال تولید شده توسط ماتریس ، همچنین دارای بردار ویژه است ، اما با ارزش خود

.

اثبات ابتدایی است. با تأیید مستقیم انجام می شود

برای یک ماتریس خود الحاقی ماتریس خود الحاقی نیز هست. بنابراین، هنجار آن توسط بزرگترین مقدار ویژه در مقدار مطلق تعیین می شود
:

.

لم 2

برای همگرا شدن روش تکرار ساده به حل سیستم برای هر انتخاب تقریب اولیه، لازم و کافی است که تمام مقادیر ویژه عملگر انتقال مدول کمتر از یک بودند:

,

کفایت. شرط به این معنی است که هنجار ماتریس ، با توجه به، کمتر از وحدت خواهد بود:
. در نتیجه می گیریم

در
.

نیاز داشتن. بیایید فرض کنیم که در بین مقادیر ویژه حداقل یکی را پیدا کرد ، که شرط لم را برآورده نمی کند ، یعنی

.

اجازه دهید عبارت صفر دنباله تکراری را در فرم انتخاب کنیم
، جایی که حل سیستم، سپس جمله صفر دنباله خطا با بردار ویژه منطبق خواهد شد. اپراتور پرش :
. در نتیجه، فرمول تکرارشونده برای اعضای زیر از دنباله خطاها به شکل زیر خواهد بود:

,
.

یعنی
. ضرورت تحقق نابرابری برای همه مقادیر ویژه برای همگرایی روش تکرار ساده ثابت شده است.

Lemma 2 برنامه ای را برای بررسی بیشتر همگرایی روش تکرار ساده تعریف می کند: لازم است محدوده تغییرات پارامتر را تنظیم کنید. که تحت آن همه مقادیر ویژه نابرابری را ارضا می کنند. انجام آن آسان است. روی انجیر 1 نمودارهای کاهش را نشان می دهد توابع خطی
. همه آنها از یک نقطه می آیند
,
و به دلیل ضرایب منفی در پایین می آیند و سریعترین عملکرد کاهش می یابد
. وقتی معنا پیدا می کند
، شرط آن متوقف می شود:

، در
.

ارزش یافت شده مرز فاصله همگرایی روش تکرار ساده است

.

ما قبلاً این نابرابری را می دانیم. قبلاً از قضیه سامارسکی به عنوان شرط کافی برای همگرایی به دست آمد. تجزیه و تحلیل اضافی بر اساس Lemma 2 به ما امکان می دهد نتیجه را اصلاح کنیم. اکنون ما مشخص کرده ایم که عضویت پارامتر تکرار است فاصله شرط لازم و کافی برای همگرایی روش تکرار ساده است.

اجازه دهید به بررسی میزان همگرایی روش بپردازیم. تخمین خطا نشان می دهد که طبق قانون یک تصاعد هندسی با مخرج کاهش می یابد.

.

شکل را در نظر بگیرید. 2، که به ما در تجزیه و تحلیل این فرمول کمک می کند. این شبیه به شکل 1 است، فقط نمودارهای غیر توابع را نشان می دهد
، و ماژول های آنها. در کوچک همه مقادیر ویژه
مثبت هستند و بزرگترین آنها مثبت است
، که با افزایش کاهش می یابد با کمترین سرعت با این حال، عبور از نقطه
مقدار خاص
، تغییر علامت، منفی می شود. در نتیجه، در حال حاضر مدول آن با افزایش است کاهش نمی یابد، بلکه افزایش می یابد
نزدیک شدن به ارزش محدود وحدت

در بخش پیدا کنید
نقطه ، که در آن تابع کاهشی است
در مقایسه با یک تابع افزایشی
. با معادله تعیین می شود

که می دهد

.

در نتیجه، دریافت می کنیم:

کوچکترین مقدار آن هنجار ماتریس است می رسد در
:

.

فرمول نشان می دهد که برای یک ماتریس بد شرط، حتی با انتخاب بهینه پارامتر تکرار
هنجار ماتریس نزدیک به وحدت است، به طوری که همگرایی روش تکرار ساده در این مورد کند می شود.

در نتیجه، ما توجه می کنیم که فرمولی که مرز فاصله همگرایی را تعیین می کند و فرمول مقدار بهینه پارامتر تکرار شونده در درجه اول مورد توجه نظری هستند. معمولاً هنگام حل SLAE، بزرگترین و کوچکترین اعداد مشخصه ماتریس هستند ناشناخته هستند، بنابراین مقادیر را محاسبه کنید و از قبل امکان پذیر نیست در نتیجه، پارامتر تکرار شونده اغلب لازم است مستقیماً در فرآیند محاسبات با آزمون و خطا انتخاب شود.

وظیفه 2.

سیستمی متشکل از دو معادله با دو مجهول را در نظر بگیرید

و با استفاده از روش تکرار ساده یک راه حل تقریبی برای آن بسازید.

بیایید بلافاصله راه حل سیستم را بنویسیم

,
,

تا بتوانید آن را با اعضای دنباله تکراری مقایسه کنید.

اجازه دهید به حل سیستم با روش تکرار ساده بپردازیم. ماتریس سیستم دارای فرم است

.

از آنجا که خود منتسب و مثبت قطعی است

اجازه دهید معادله مشخصه ماتریس را بسازیم و ریشه های آن را پیدا کنید:

,

,

می توان از آنها برای تعیین مرز فاصله همگرایی استفاده کرد و مقدار بهینهپارامتر تکرار :

,
.

برای ساخت یک دنباله تکراری، مقداری از پارامتر تکرار شونده را در بازه همگرایی انتخاب می کنیم، به عنوان مثال،
. در این مورد، فرمول تکرار شونده برای عبارات دنباله تکراری به شکل زیر است:

، جایی که

ساده ترین تقریب اولیه را در نظر بگیرید
و چند عبارت اول دنباله تکراری را بنویسید ، برای هر یک از آنها اختلاف محاسبه می شود
. در نتیجه، دریافت می کنیم:

,
,
,

,
,
,

,
,
,

,
,
.

هنجار باقیمانده ها، اگرچه به آرامی، اما کاهش می یابد، که نشان دهنده همگرایی فرآیند است. همین را می توان از مقایسه اصطلاحات دنباله تکراری مشاهده کرد با حل سیستم همگرایی کند به دلیل شرطی بودن ضعیف ماتریس است :

.

مزیت روش‌های تکراری، کاربرد آن‌ها برای سیستم‌ها و سیستم‌های با شرایط نامناسب، اصلاح خود و سهولت پیاده‌سازی در رایانه شخصی است. روش های تکراری برای شروع محاسبه نیاز به تقریب اولیه به راه حل مورد نظر دارند.

لازم به ذکر است که شرایط و سرعت همگرایی فرآیند تکراری اساساً به ویژگی های ماتریس بستگی دارد. ولیسیستم و انتخاب تقریب های اولیه.

برای اعمال روش تکرار، سیستم اصلی (2.1) یا (2.2) باید به شکل کاهش یابد.

پس از آن فرآیند تکراری طبق فرمول های تکراری انجام می شود

, ک = 0, 1, 2, ... . (2.26آ)

ماتریس جیو بردار در نتیجه تبدیل سیستم (2.1) به دست می آید.

برای همگرایی (2.26 آ) برای |ل لازم و کافی است من(جی)| < 1, где lمن(جی) همه مقادیر ویژه ماتریس هستند جی. همگرایی نیز در صورت || رخ خواهد داد جی|| < 1, так как |lمن(جی)| < " ||جی||، جایی که "هر کدام است.

نماد || ... || به معنای هنجار ماتریس است. هنگام تعیین مقدار آن، آنها اغلب در بررسی دو شرط متوقف می شوند:

||جی|| = یا || جی|| = , (2.27)

جایی که . اگر ماتریس اصلی باشد، همگرایی تضمین می شود ولیدارای غلبه مورب است، یعنی.

. (2.28)

اگر (2.27) یا (2.28) ارضا شود، روش تکرار برای هر تقریب اولیه همگرا می شود. اغلب، بردار به صورت صفر یا واحد در نظر گرفته می شود، یا خود بردار از (2.26) گرفته می شود.

رویکردهای زیادی برای تبدیل سیستم اصلی (2.2) با ماتریس وجود دارد ولیبرای اطمینان از فرم (2.26) یا برای ارضای شرایط همگرایی (2.27) و (2.28).

به عنوان مثال، (2.26) را می توان به صورت زیر به دست آورد.

اجازه دهید ولی = AT+ از جانب، دت AT¹ 0; سپس ( ب+ از جانب)= Þ ب= −سی+ Þ Þ ب –1 ب= −ب –1 سی+ ب–1، از آنجا = − ب –1 سی+ ب –1 .

قرار دادن - ب –1 سی = جی, ب-1 = ، (2.26) را بدست می آوریم.

از شرایط همگرایی (2.27) و (2.28) مشاهده می شود که نمایندگی ولی = AT+ از جانبنمی تواند دلخواه باشد

اگر ماتریس ولیشرایط (2.28) و سپس به عنوان یک ماتریس را برآورده می کند ATشما می توانید مثلث پایین را انتخاب کنید:

, a II ¹ 0.

; Þ ; Þ ; Þ

با انتخاب پارامتر a می توانیم اطمینان حاصل کنیم که || جی|| = ||E+ الف آ|| < 1.

اگر (2.28) غالب باشد، تبدیل به (2.26) را می توان با حل هر یک انجام داد. منمعادله سیستم (2.1) نسبت به x iبا توجه به فرمول های بازگشتی زیر:

(2.28آ)

اگر در ماتریس ولیهیچ برتری مورب وجود ندارد، باید با کمک برخی تبدیلات خطی که معادل آنها را نقض نمی کند، به دست آید.

به عنوان مثال، سیستم را در نظر بگیرید

(2.29)

همانطور که مشاهده می شود، در معادلات (1) و (2) تسلط مورب وجود ندارد، اما در (3) وجود دارد، بنابراین آن را بدون تغییر می گذاریم.

اجازه دهید در رابطه (1) به تسلط مورب دست یابیم. (1) را در a، (2) در b ضرب کنید، هر دو معادله را اضافه کنید، و a و b را در معادله حاصل انتخاب کنید تا تسلط مورب وجود داشته باشد:

(2a + 3b) ایکس 1 + (-1.8a + 2b) ایکس 2 + (0.4a - 1.1b) ایکس 3 = الف.

با گرفتن a = b = 5، 25 به دست می آید ایکس 1 + ایکس 2 – 3,5ایکس 3 = 5.

برای تبدیل معادله (2) با غالب (1)، در g ضرب می کنیم، (2) در d ضرب می کنیم و (1) را از (2) کم می کنیم. گرفتن

(3 بعدی - 2 گرم) ایکس 1+(2d+1.8g) ایکس 2 + (-1.1 روز - 0.4 گرم) ایکس 3 = −g.

با قرار دادن d = 2، g = 3، 0 می گیریم ایکس 1 + 9,4 ایکس 2 – 3,4 ایکس 3 = -3. در نتیجه، سیستم را دریافت می کنیم

(2.30)

از این تکنیک می توان برای یافتن راه حل برای دسته وسیعی از ماتریس ها استفاده کرد.

یا

با در نظر گرفتن تقریب اولیه بردار = (0.2; -0.32; 0) تی، ما این سیستم را با استفاده از فناوری حل خواهیم کرد (2.26 آ):

ک = 0, 1, 2, ... .

فرآیند محاسبه زمانی متوقف می شود که دو تقریب همسایه بردار راه حل از نظر دقت بر هم منطبق باشند، یعنی.

.

فناوری حل تکراری شکل (2.26 آ) نامیده می شود با تکرار ساده .

مقطع تحصیلی خطای مطلقبرای روش تکرار ساده:

جایی که نماد || ... || یعنی هنجار

مثال 2.1. با استفاده از روش تکرار ساده با دقت e = 0.001 سیستم معادلات خطی را حل کنید:

تعداد مراحلی که پاسخی دقیق به 0.001 e = می دهد را می توان از رابطه تعیین کرد

0.001 پوند

اجازه دهید همگرایی را با فرمول (2.27) تخمین بزنیم. اینجا || جی|| = = حداکثر (0.56; 0.61; 0.35; 0.61) = 0.61< 1; = 2,15. Значит, сходимость обеспечена.

به عنوان تقریب اولیه، بردار عبارات آزاد را می گیریم، یعنی = (2.15; -0.83; 1.16; 0.44) تی. مقادیر بردار را در (2.26 آ):

در ادامه محاسبات، نتایج را در جدول وارد می کنیم:

ک	ایکس 1	ایکس 2	ایکس 3	ایکس 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

همگرایی در هزارم در مرحله دهم اتفاق می افتد.

پاسخ: ایکس 1 » 3.571; ایکس 2 » -0.957; ایکس 3 » 1.489; ایکس 4 "-0.836.

این محلول را می توان با استفاده از فرمول های (2.28 آ).

مثال 2.2. برای نشان دادن الگوریتم با استفاده از فرمول (2.28 آ) راه حل سیستم را در نظر بگیرید (فقط دو تکرار):

; . (2.31)

اجازه دهید سیستم را به شکل (2.26) مطابق (2.28) تبدیل کنیم آ):

Þ (2.32)

بیایید تقریب اولیه را در نظر بگیریم = (0; 0; 0) تی. سپس برای ک= 0 ارزش آشکار = (0.5; 0.8; 1.5) تی. اجازه دهید این مقادیر را با (2.32) جایگزین کنیم، یعنی برای ک= 1 بدست می آوریم = (1.075; 1.3; 1.175) تی.

خطا e 2 = = max(0.575; 0.5; 0.325) = 0.575.

بلوک دیاگرام الگوریتم برای یافتن جواب SLAE با روش تکرارهای سادهطبق فرمول های کاری (2.28 آ) در شکل نشان داده شده است. 2.4.

یکی از ویژگی های بلوک دیاگرام وجود بلوک های زیر است:

- بلوک 13 - هدف آن در زیر مورد بحث قرار گرفته است.

- بلوک 21 - نمایش نتایج روی صفحه؛

- بلوک 22 - تأیید (شاخص) همگرایی.

اجازه دهید طرح پیشنهادی را بر اساس مثال سیستم (2.31) تحلیل کنیم ( n= 3، w = 1، e = 0.001):

= ; .

مسدود کردن 1. داده های اولیه را وارد کنید آ, , w , e , n: n= 3، w = 1، e = 0.001.

چرخه I. مقادیر اولیه بردارها را تنظیم کنید ایکس 0منو x i (من = 1, 2, 3).

مسدود کردن 5. شمارنده تعداد تکرارها را تنظیم مجدد کنید.

مسدود کردن 6. شمارنده خطای فعلی را بازنشانی کنید.

ATحلقه II شماره ردیف های ماتریس را تغییر می دهد ولیو بردار .

چرخه دوم:من = 1: س = ب 1 = 2 (بلوک 8).

به حلقه تو در تو III، block9 بروید - شمارنده اعداد ستون های ماتریس ولی: j = 1.

مسدود کردن 10: j = منبنابراین به بلوک 9 برمی گردیم و افزایش می دهیم jدر هر واحد: j = 2.

در بلوک 10 j ¹ من(2 ¹ 1) - به بلوک 11 بروید.

مسدود کردن 11: س= 2 – (–1) × ایکس 0 2 \u003d 2 - (-1) × 0 \u003d 2، به بلوک 9 بروید، که در آن jیک افزایش دهید: j = 3.

در بلوک 10، شرایط j ¹ مناجرا شد، بنابراین به بلوک 11 بروید.

مسدود کردن 11: س= 2 – (–1) × ایکس 0 3 \u003d 2 - (-1) × 0 \u003d 2، پس از آن به بلوک 9 می رویم که در آن jیک افزایش ( j= 4). معنی jبیشتر n (n= 3) - حلقه را پایان دهید و به بلوک 12 بروید.

مسدود کردن 12: س = س / آ 11 = 2 / 4 = 0,5.

مسدود کردن 13: w = 1; س = س + 0 = 0,5.

مسدود کردن 14: د = | x i – س | = | 1 – 0,5 | = 0,5.

مسدود کردن 15: x i = 0,5 (من = 1).

مسدود کردن 16. شرایط را بررسی کنید د > de: 0.5 > 0، بنابراین به بلوک 17 بروید که در آن تخصیص داده ایم de= 0.5 و برگرداندن با مرجع " ولی» به مرحله بعدی چرخه II - به بلوک 7 که در آن منیک افزایش دهد.

چرخه دوم: من = 2: س = ب 2 = 4 (بلوک 8).

j = 1.

از طریق بلوک 10 j ¹ من(1 ¹ 2) - به بلوک 11 بروید.

مسدود کردن 11: س= 4 – 1 × 0 = 4، به بلوک 9 بروید، که در آن jیک افزایش دهید: j = 2.

در بلوک 10 شرط برقرار نیست، بنابراین به بلوک 9 می رویم که در آن jیک افزایش دهید: j= 3. بر اساس قیاس به بلوک 11 می گذریم.

مسدود کردن 11: س= 4 – (–2) × 0 = 4، پس از آن چرخه III را تمام کرده و به بلوک 12 می رویم.

مسدود کردن 12: س = س/ آ 22 = 4 / 5 = 0,8.

مسدود کردن 13: w = 1; س = س + 0 = 0,8.

مسدود کردن 14: د = | 1 – 0,8 | = 0,2.

مسدود کردن 15: x i = 0,8 (من = 2).

مسدود کردن 16. شرایط را بررسی کنید د > de: 0,2 < 0,5; следовательно, возвращаемся по ссылке «ولی» به مرحله بعدی چرخه II - تا بلوک 7.

چرخه دوم: من = 3: س = ب 3 = 6 (بلوک 8).

به حلقه تودرتو III، block9 بروید: j = 1.

مسدود کردن 11: س= 6 – 1 × 0 = 6، به بلوک 9 بروید: j = 2.

از طریق بلوک 10 به بلوک 11 می رویم.

مسدود کردن 11: س= 6 – 1 × 0 = 6. چرخه III را تمام کرده و به بلوک 12 بروید.

مسدود کردن 12: س = س/ آ 33 = 6 / 4 = 1,5.

مسدود کردن 13: س = 1,5.

مسدود کردن 14: د = | 1 – 1,5 | = 0,5.

مسدود کردن 15: x i = 1,5 (من = 3).

طبق بلوک 16 (با در نظر گرفتن مراجع" ولی"و" از جانب”) از چرخه II خارج شده و به بلوک 18 بروید.

مسدود کردن 18. تعداد تکرارها را افزایش دهید آی تی = آی تی + 1 = 0 + 1 = 1.

در بلوک های 19 و 20 سیکل IV، مقادیر اولیه را جایگزین می کنیم ایکس 0منمقادیر دریافتی x i (من = 1, 2, 3).

مسدود کردن 21. چاپ مقادیر میانیتکرار فعلی، در این مورد: = (0.5; 0.8; 1.5) تی, آی تی = 1; de = 0,5.

به چرخه II در بلوک 7 بروید و محاسبات در نظر گرفته شده را با مقادیر اولیه جدید انجام دهید ایکس 0من (من = 1, 2, 3).

پس از آن می گیریم ایکس 1 = 1,075; ایکس 2 = 1,3; ایکس 3 = 1,175.

در اینجا روش سیدل همگرا می شود.

با فرمول (2.33)

ک	ایکس 1	ایکس 2	ایکس 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

پاسخ: ایکس 1 = 0,248; ایکس 2 = 1,115; ایکس 3 = –0,224.

اظهار نظر. اگر برای یک سیستم تکرار ساده و روش سیدل همگرا شوند، روش سیدل ارجح است. با این حال، در عمل، حوزه های همگرایی این روش ها ممکن است متفاوت باشد، به عنوان مثال، روش تکرار ساده همگرا می شود، در حالی که روش سیدل واگرا می شود، و بالعکس. برای هر دو روش، اگر || جی|| نزدیک به واحد، میزان همگرایی بسیار پایین است.

برای تسریع همگرایی، از یک تکنیک مصنوعی استفاده می شود - به اصطلاح روش آرام سازی . ماهیت آن در این واقعیت نهفته است که مقدار بعدی با روش تکرار به دست می آید x i (ک) طبق فرمول دوباره محاسبه می شود

جایی که w معمولا از 0 به 2 (0) تغییر می کند< w £ 2) с каким-либо шагом (ساعت= 0.1 یا 0.2). پارامتر w طوری انتخاب می شود که همگرایی روش در حداقل تعداد تکرار حاصل شود.

آرامش- تضعیف تدریجی هر حالتی از بدن پس از قطع عوامل ایجاد کننده این حالت (فیزیکی. فنی).

مثال 2.4. نتیجه تکرار پنجم را با استفاده از فرمول آرامش در نظر بگیرید. بیایید w = 1.5 را در نظر بگیریم:

همانطور که می بینید نتیجه تقریباً هفتمین تکرار به دست آمده است.

روش تکرارهای ساده بر اساس جایگزینی معادله اصلی با یک معادله معادل است:

اجازه دهید تقریب اولیه با ریشه مشخص شود x = x 0. با جایگزین کردن آن در سمت راستدر معادله (2.7)، یک تقریب جدید به دست می آوریم ، سپس به روشی مشابه دریافت می کنیم و غیره.:

. (2.8)

نه در همه شرایط، فرآیند تکراری به ریشه معادله همگرا می شود ایکس. بیایید این روند را با جزئیات بیشتری در نظر بگیریم. شکل 2.6 نشان می دهد تفسیر گرافیکیفرآیند همگرا و واگرا یک طرفه شکل 2.7 فرآیندهای همگرا و واگرا دو طرفه را نشان می دهد. یک فرآیند واگرا با افزایش سریع مقادیر آرگومان و تابع و خاتمه غیرعادی برنامه مربوطه مشخص می شود.

با یک فرآیند دو طرفه، یک حلقه امکان پذیر است، یعنی تکرار بی پایان همان مقادیر تابع و آرگومان. حلقه کردن یک فرآیند واگرا را از یک فرآیند همگرا جدا می کند.

از نمودارها می توان دریافت که در هر دو فرآیند یک طرفه و دو طرفه، همگرایی به ریشه با شیب منحنی نزدیک ریشه تعیین می شود. هر چه شیب کمتر باشد، همگرایی بهتر است. همانطور که می دانید مماس شیب منحنی برابر با مشتق منحنی در یک نقطه معین است.

بنابراین، هرچه نزدیک ریشه کمتر باشد، روند سریعتر همگرا می شود.

برای اینکه فرآیند تکرار شونده همگرا باشد، نابرابری زیر باید در مجاورت ریشه برآورده شود:

انتقال از معادله (2.1) به معادله (2.7) قابل انجام است روش های مختلفبسته به نوع عملکرد f(x).در چنین انتقالی، لازم است تابعی به گونه ای ساخته شود که شرط همگرایی (2.9) برآورده شود.

یکی از الگوریتم های کلی برای انتقال از معادله (2.1) به معادله (2.7) را در نظر بگیرید.

سمت چپ و راست معادله (2.1) را در یک ثابت دلخواه ضرب می کنیم بو مجهول را به هر دو قسمت اضافه کنید ایکس.در این حالت، ریشه های معادله اصلی تغییر نمی کند:

نماد را معرفی می کنیم و از رابطه (2.10) به معادله (2.8) عبور کنید.

انتخاب خودسرانه ثابت بتحقق شرط همگرایی (2.9) را تضمین خواهد کرد. شرط (2.2) معیار خاتمه فرآیند تکراری خواهد بود. شکل 2.8 یک تفسیر گرافیکی از روش تکرارهای ساده با روش نمایش توصیف شده را نشان می دهد (مقیاس ها در امتداد محورهای X و Y متفاوت هستند).

اگر تابع به شکل انتخاب شود، مشتق این تابع خواهد بود. بالاترین نرخ همگرایی در آن صورت خواهد بود و فرمول تکرار شونده (2.11) به فرمول نیوتن می رود. بنابراین، روش نیوتن بیشترین میزان را دارد درجه بالاهمگرایی از تمام فرآیندهای تکراری

پیاده سازی نرم افزاری روش تکرارهای ساده در قالب یک رویه زیر روال انجام می شود Iteras(برنامه 2.1).

کل رویه عملاً شامل یک حلقه تکرار ... تا زمانی است که فرمول (2.11) را با در نظر گرفتن شرط خاتمه فرآیند تکراری (فرمول (2.2)) پیاده سازی می کند.

محافظت از حلقه با شمارش تعداد حلقه ها با استفاده از متغیر Niter در رویه ایجاد می شود. در تمرین های عملیلازم است با اجرای برنامه بررسی شود که انتخاب ضریب چگونه تأثیر می گذارد بو تقریب اولیه در روند یافتن ریشه. هنگام تغییر ضریب بماهیت فرآیند تکراری برای تابع مورد مطالعه تغییر می کند. ابتدا دو طرفه می شود و سپس حلقه می شود (شکل 2.9). مقیاس در امتداد محورها ایکسو Yناهمسان. مدول b حتی بزرگتر منجر به یک فرآیند واگرا می شود.

مقایسه روش های حل تقریبی معادلات

مقایسه روش هایی که در بالا توضیح داده شد حل عددیمعادلات با استفاده از برنامه ای انجام شد که به شما امکان می دهد روند پیدا کردن ریشه را مشاهده کنید فرم گرافیکی. رویه های موجود در این برنامه و اجرای روش های مقایسه شده در زیر آورده شده است (برنامه 2.1).

برنج. 2.3-2.5، 2.8، 2.9 کپی هایی از صفحه کامپیوتر در پایان فرآیند تکراری هستند.

در تمام موارد، ما تابع مورد مطالعه را در نظر گرفتیم معادله درجه دوم x 2 -x-6 = 0، دارای یک راه حل تحلیلی x 1 = -2 و x 2 = 3. خطا و تقریب های اولیه برای همه روش ها یکسان در نظر گرفته شد. نتایج جستجوی ریشه x= 3 نشان داده شده در شکل ها به شرح زیر است. روش دوگانگی کندترین - 22 تکرار، سریعترین - روش تکرارهای ساده را در b = -0.2 - 5 تکرار همگرا می کند. در اینجا هیچ تناقضی با این جمله که روش نیوتن سریعترین است وجود ندارد.

مشتق تابع مورد مطالعه در یک نقطه ایکس= 3 برابر با 0.2- است، یعنی محاسبه در این مورد عملاً با روش نیوتن با مقدار مشتق در نقطه ریشه معادله انجام شده است. هنگام تغییر ضریب بنرخ همگرایی کاهش می یابد و فرآیند همگرای تدریجی ابتدا چرخه می شود، سپس واگرا می شود.