پنجشنبه ۱۰ اردیبهشت ۱۳۹۴ 8189 0 10

حذف گاوسی (Gaussian elimination) روشی در جبر خطی برای حل دستگاه معادلات خطی است.

مفاهیم ریاضی:

حذف گاوسی

حذف گاوسی (Gaussian elimination) روشی در جبر خطی برای حل دستگاه معادلات خطی است. این روش، به صورت انجام عملیات متوالی بر روی ماتریس ضرایب است. از این روش، همچنین برای یافتن مرتبه‌ی یک ماتریس، محاسبه‌ی دترمینان ماتریس و محاسبه‌ی معکوس یک ماتریس مربعی معکوس‌پذیر استفاده می‌شود. نام این روش از ریاضی‌دان آلمانی کارل فریدریش گاوس¹ گرفته شده است. برای انجام عملیات کاهش سطح در یک ماتریس از یک سری عملیات پایه برروی سطر های ماتریس استفاده می شود. تاماکسیمم مقدار ممکن از درایه های زیر قطر اصلی ماتریس برابر صفر شوند. سه نوع از عملیات پایه برروی سطرهای ماتریس وجود دارد:

1- جابجایی دوردیف از سطرها.

2-ضرب کردن یک سطر از ماتریس در یک عدد غیر صفر.

3-جمع کردن یک سطر با سطر دیگر.

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

پیچیدگی محاسباتی
پیچیدگی محاسباتی هر الگوریتم با تعداد اجرای هر سطر از آن در کامپیوتر مرتبط است و با نماد بیگ او² به فرم (O(n نشان داده می شود. برای مثال برای محاسبه مساله ای با n معادله و n مجهول به روش حذف گاوسی تعداد عمل تقسیم و تعداد عمل ضرب و تعداد عمل تفریق در مجموع به طور تقریبی 2n3/3 می باشد. بنابراین پیچیدگی ریاضی الگورتیم از مرتبه (O(n3 است.

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

''Find the k-th pivot:''
i_max := [[argmax]] (i = k ... m, abs(A[i, k]))
'''if''' A[i_max, k] = 0
'''error''' "Matrix is singular!"
'''swap rows'''(k, i_max)
''Do for all rows below pivot:''
'''for''' i = k + 1 ... m:
''Do for all remaining elements in current row:''
'''for''' j = k + 1 ... n:
A[i, j] := A[i, j] - A[k, j] * (A[i, k] / A[k, k])
''Fill lower triangular matrix with zeros:''
A[i, k] := 0

بیشتر بدانید...

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

Gaussian Elimination

Wikipedia: Gaussian Elimination

پی نوشت و منابع ...

پی نوشت:

1. Johann Carl Friedrich Gauß

2. Big O Notation

منابع:

-- جبر خطّی عددی (انگلیسی)
-- مقدمه‌ای بر ریاضیات کاربردی

منبع

دانشنامه ویکیپدیا

کلمات کلیدی

مفاهیم ریاضی کارل فریدریش گاوس

سایر مطالب پیشنهادی آی هوش:

9031

دستگاه شمارش

27263

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

24606

تعاریف و مفاهیم ریاضی: اصل لانه کبوتری

14040

تابع دوسویی

18876

تعاریف و مفاهیم ریاضی: حسابان چیست؟

7926

هوش اینشتین

14610

هم‌ریختی (همومورفیسم)

27463

جدول ضرب هگزادسیمال

9964

کاریکاتور/ کارل فردریش گاوس

4794

۳۰ آوریل، زادروز شاهزاده ریاضیدانان

36105

الگوریتم: غربال اراتوستن

20830

اعداد خوشحال

آی هوش: گنجینه دانستنی ها و معماهای هوش و ریاضی

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

آی هوش: مرجع مفاهیم هوش و ریاضی و انواع تست هوش، معمای ریاضی و معمای شطرنج

در زمینه‌ی انتشار نظرات مخاطبان، رعایت برخی موارد ضروری است:

-- لطفاً نظرات خود را با حروف فارسی تایپ کنید.
-- آی هوش مجاز به ویرایش ادبی نظرات مخاطبان است.
-- آی هوش از انتشار نظراتی که در آنها رعایت ادب نشده باشد معذور است.
-- نظرات پس از تأیید مدیر بخش مربوطه منتشر می‌شود.

نظر شما

ارسال