ضرب ماتریس
الگوریتم ضرب زنجیری ماتریس ها
مساله ضرب زنجیری ماتریسها و پرانتزبندی بهینه آن یکی از مثالهای مشهور کاربرد برنامه نویسی پویا در حل مسائل بهینه سازی است. فرض کنید قصد داریم حاصلضرب عبارت ماتریسی A3 x 7 x B7 x 8 x C8 x 4 را محاسبه کنیم. می دانیم که ضرب ماتریسها خاصیت شرکت پذیری دارند و ترتیب ضرب آنها مهم نیست. پرانتزبندی های مختلف ضرب ماتریس ها حالتهای مختلف محاسبه آن را به ما می دهند: 1: A x ( B x C ) 2: ( A x B ) x C در حالت اول ابتدا B در C ضرب شده و سپس حاصل آنها در A ضرب می شود، و در حالت دوم ابتدا A و B در هم ضرب شده و سپس نتیجه در C ضرب می شود. حال سوال این است که آیا این پرانتزبندی ها تفاوتی با هم دارند؟ ضرب ماتریس دلخواه MR x L در ماتریس دلخواه دیگری مانند NL x C به R x L x C عمل ضرب عددی نیاز دارد (چرا؟). با توجه به این موضوع، تعداد کل عملهای ضرب برای محاسبه حاصلضرب سه ماتریس فوق را در هر دو پرانتزبندی محاسبه می کنیم: 1: A x ( B x C ) : 7 x 8 x 4 + 3 x 7 x 4 = 308 در حالت اول ابتدا ماتریس B در C ضرب می شود. سپس ماتریس A و ماتریس حاصل از ضرب اول، با ابعاد ( ۴ , ۷ )، در هم ضرب می شوند. به همین ترتیب در مورد حالت دوم داریم: 2: ( A x B ) x C : 3 x 7 x 8 + 3 x 8 x 3 = 240 پس در پرانتزبندی به فرم دوم تعداد ضرب کمتری نیاز است. ثابت شده است که تعداد کل حالتهای پرانتزبندی ضرب زنجیری n ماتریس، مطابق با جملات دنباله اعداد کاتالان هستند: هدف ما این است که در بین تمامی این حالت ها، حالتی را بیابیم که حاصل ضرب ماتریسها با حداقل ضرب عددی محاسبه شود. روش تقسیم و حل (Divide and Conquer): ابتدا سعی می کنیم با استفاده از روش تقسیم و حل الگوریتمی برای پاسخ مساله پیدا کنیم. برای اینکار عبارت مورد نظر را به دو قسمت تقسیم می کنیم. به عنوان مثال فرض کنید n = 7 باشد. در این صورت به شش طریق می توان عبارت را به دو دسته تقسیم کرد: 1: ( M1 ) x ( M2 x M3 x M4 x M5 x M6 x M7 ) 2: ( M1 x M2 ) x ( M3 x M4 x M5 x M6 x M7 ) 3: ( M1 x M2 x M3 ) x ( M4 x M5 x M6 x M7 ) 4: ( M1 x M2 x M3 x M4 ) x ( M5 x M6 x M7 ) 5: ( M1 x M2 x M3 x M4 x M5 ) x ( M6 x M7 ) 6: ( M1 x M2 x M3 x M4 x M5 x M6 ) x ( M7 ) هر کدام از حاصلضربهای داخل پرانتزها، زیر مساله ای با n < 7 هستند. همانطور که می دانید در ضرب دو ماتریس، تعداد ستونهای ماتریس اول با تعداد سطرهای ماتریس دوم برابر است. در نتیجه ابعاد هفت ماتریس فوق را به صورت زیر می توان خلاصه کرد: d0 , d1 , d2 , d3 , d4 , d5 , d6 , d7 که ماتریس اول d0 سطر و d1 ستون، ماتریس دوم d1 سطر و d2 ستون، . . . و ماتریس هفتم d6 سطر و d7 ستون دارد. حال تابع Mult را به گونه ای تعریف می کنیم که حداقل ضربهای مورد نیاز برای ضرب ماتریسهای iام تا jام را محاسبه کند. در این صورت برای شش حالت فوق داریم: 1: ( M1 ) x ( M2 x M3 x M4 x M5 x M6 x M7 ) : min1 = Mult( 1, 1 ) + Mult( 2, 7 ) + d0 d1 d7 2: ( M1 x M2 ) x ( M3 x M4 x M5 x M6 x M7 ...
ماتریسها
در ریاضیات ماتریس عبارت است یک جدول مستطیلی از اعداد و یا به صورت ساخت یافته‌تر: ماتریس مجموعه‌ای از اشیای هم نوع است که به تعدادی گروه با اعضای یکسان تقسیم بندی شده است. ماتریسها ریاضیات مناسبی برای ثبت و ذخیره داده‌هایی هستند که مقادیر آنها به دو کمیت بستگی دارد. از این جهت چون در اکثر علوم با چنین داده‌هایی روبرو می‌شویم. بنابراین کاربرد وسیع ماتریسها در اکثر شاخه‌های علوم مهندسی میشود. ماتریس ماتریس عبارت است از آرایشی (آرایه‌ای) مستطیل شکل از اعداد مختلط به طوری که عناصر این آرایه را درایه می‌نامیم و عنصر واقع در سطر ام و ستون ام را با نماد نشان می‌دهیم. ماتریسی که دارای سطر و ستون باشد را ماتریس از مرتبه در می‌نامیم.( ) نکته هرگاه آنگاه ماتریس را مربع از مرتبه می‌نامیم. یک ماتریس را بصورت نمایش می‌دهیم. تاریخچه مطالعه روی انواع خاصی از ماتریسها مانند مربعهای جادویی و مربعهای لاتین ، به تاریخ قبل از میلاد نسبت داده شده است. معرفی و تکامل نمایش ماتریسها به عنوان شاخه‌ای از جبر خطی در نتیجه مطلعه روی ضرایب سیستم معادلات خطی و الگوها و روشهای حل آنها بوجود آمد. لایب نیتس به عنوان یکی از پایه گذاران علم حسابان در سال 1693، دترمینان ماتریسها را معرفی کرد. در ادامه کرامر روش خود را برای حل دستگاه معادلات خطی بر اساس دترمینان ماتریس ضرایب دستگاه معرفی کرد. این روش که به روش کرامر مرسوم است، بر اساس استفاده صریح از دترمینان ماتریس ضرایب معرفی گردیده است. در مقابل اولین استفاده ضمنی از ماتریسها توسط لاگرانژ برای تعیین ماکزیمم و مینیمم توابع چند مقداری مورد استفاده قرار گرفت. در ادامه گاوس روش حذفی خود را برای حل مسائل کمترین مربعات که کاربردهای بسیار وسیعی در علوم سماوی و ژئودوزی دارد را معرفی کرد. روابط بین ماتریسها تساوی دو ماتریس دو ماتریس و مساوی اند اگر و فقط اگر (هم مرتبه باشند) و جمع دو ماتریس اگر و آنگاه قرینه ماتریس اگر آنگاه قرینه را بصورت زیر تعریف میکنیم: ضرب اسکالر در ماتریس اگر و یک اسکالر باشد آنگاهدر ضرب اسکالر یک عدد در یک ماتریس ضرب میشود. در این نوع ضرب تمامی عناصر ماتریس در آن عدد ضرب می‌شوند به عنوان مثال: و نمایش ریاضی آن به صورت زیر می باشد: cA)ij = c(A)ij) ضرب ماتریسها اگر و آنگاه ضرب دو ماتریس را با علامت نمایش داده و بصورت زیر تعریف خواهیم کرد: در این نوع هر دو ضرب شونده و ضرب کننده از نوع ماتریس می‌باشند. بطور مشابه ضرب دو ماتریس نیز باید یک جنبه خوش تعریفی داشته باشد. ضرب دو ماتریس داده شده A و B زمانی خوش تعریف است که تعداد ستونهای ماتریس ضرب کننده با ...
ضرب دو ماتریس و محاسبه ی دترمینان ماتریس n*n
مقدمه هدف اصلی از انجام پروژه های برنامه های برنامه نویسی اشنایی با انجام کار شامل درک صحیح از مساله، طراحی فلوچارت و پیاده سازی انها در یک زبان برنامه نویسی است. هدف از انجام این پروژه نوشتن برنامه ای به زباتن فرترن است که حاصل ضرب دوماتریس A(M*N) و B(N*M) را محاسبه کند و دترمینان ماتریس حاصل ضرب را چاپ کند. در انجام این پروژه از زبان برنامه نویسی فرترن استفاده کرده ایم. درواقع قواعد اساسی تمامی زبان های برنامه نویسی تقریبا یکسان است،به این دلیل که همگی میخواهند الگوریتم را به یک زبان قابل فهم برای رایانه تبدیل کنند.انچه موجب قدرتمندی یک زبان نسبت به زبان دیگر میشود،ظریف کاری هایی است که دریک زبان با زبان دیگرفرق میکند.علت انتخاب زبان برنامه نویسی فرترن هم بدین خاطر است که برای محاسبات عددی در رشته های علوم پایه و مهندسی بسیارمناسب بوده وقابلیت انعطاف زیادی دارد. تئوری کار الگوریتم به معنی تشریح دقیق مراحل مختلف ونحوه انجام کار به خصوصی است. بطور کلی الگوریتم ازبخش های مختلفی تشکیل میشود که برای این برنامه بصورت زیر است: الف)تعریف دقیق مسئله:دراین برنامه میخواهیم حاصل ضرب دو ماتریسَA(M*N) وB(N*M) را محاسبه کنیم .درحقیقت دراین برنامه قصد داریم با وارد کردن درایه های دو ماتریس A و B، ماتریس حاصلضرب C(M*M) را بدست اوریم سپس از روش بالا مثلثی دترمینان ماتریس حاصلضرب را محاسبه کند. ب) ورودی های مساله:ابعاد و درایه ها ج)عملیات: با استفاده از عملیات ریاضی ربطه بین ماتریس های A و B با ماتریس حاصل ضرب مشخص میشود.به طور کلی درایه C(I,J) در ماتریس حاصل ضرب، ازضرب سطر i ام ماتریس A در ستون J ام ماتریس B به صورت زیر بدست می آید. C(I,j)=(A(i,1)*B(1,j) ) + (A(I,2) * B(2,J) ) + ……( A(I,n)*B(n,J) ) برای محاسبه دترمینان از روش بالا مثلثی استفاده میکنیم. در این روش با استفاده از فرمولهای ماتریسی درایه های پایین قطر اصلی را صفر می کنیم و سپس دترمینان ماتریس، حاصلضرب درایه های قطر اصلی می شود. د)خروجی های مساله:ماتریس C(N,N) که حاصلضرب دو ماتریس Aو B است. DET ماتریسC. ویژگی اصلی در طراحی این برنامه استفاده از ساختار کنترلی FOR, NEXT میباشد. در حقیقت برای ورود درایه های دو ماتریس A و B و همچنین محاسبه ماتریس حاصل ضرب نیازمند این بودیم تا بخشی ار ان بطور مکرر تکرار شود،لذا برای پرهیز از این تکرار از ساختار for,nextاستفاده کردیمکد برنامه به زبان فرترن PROGRAM GROUP INTEGER ::I,J,M,N,S,K,G=2,T=0,SUM=0,Q REAL::DET=1 REAL,DIMENSION(:,:),ALLOCATABLE::A REAL,DIMENSION(:,:),ALLOCATABLE::B REAL,DIMENSION(:,:),ALLOCATABLE::C "PRINT*,"ENTER M,N READ*,M,N ((ALLOCATE(A(N,M ((ALLOCATE(B(M,N((ALLOCATE(C(N,N "("PRINT*,"Enter A("N","M READ*,A "("PRINT*,"Enter B("M","N READ*,B DO I=1,N DO ...
ماتریس
ماتریس ماتریس عبارت است از آرایشی (آرایه‌ای) مستطیل شکل از اعداد مختلط به طوری که عناصر این آرایه را درایه می‌نامیم و عنصر واقع در سطر ام و ستون ام را با نماد نشان می‌دهیم. ماتریسی که دارای سطر و ستون باشد را ماتریس از مرتبه در می‌نامیم.( ) نکته هرگاه آنگاه ماتریس را مربع از مرتبه می‌نامیم. یک ماتریس را بصورت نمایش می‌دهیم. تاریخچه مطالعه روی انواع خاصی از ماتریسها مانند مربعهای جادویی و مربعهای لاتین ، به تاریخ قبل از میلاد نسبت داده شده است. معرفی و تکامل نمایش ماتریسها به عنوان شاخه‌ای از جبر خطی در نتیجه مطلعه روی ضرایب سیستم معادلات خطی و الگوها و روشهای حل آنها بوجود آمد. لایب نیتس به عنوان یکی از پایه گذاران علم حسابان در سال 1693، دترمینان ماتریسها را معرفی کرد. در ادامه کرامر روش خود را برای حل دستگاه معادلات خطی بر اساس دترمینان ماتریس ضرایب دستگاه معرفی کرد. این روش که به روش کرامر مرسوم است، بر اساس استفاده صریح از دترمینان ماتریس ضرایب معرفی گردیده است. در مقابل اولین استفاده ضمنی از ماتریسها توسط لاگرانژ برای تعیین ماکزیمم و مینیمم توابع چند مقداری مورد استفاده قرار گرفت. در ادامه گاوس روش حذفی خود را برای حل مسائل کمترین مربعات که کاربردهای بسیار وسیعی در علوم سماوی و ژئودوزی دارد را معرفی کرد. روابط بین ماتریسها تساوی دو ماتریس دو ماتریس و مساوی اند اگر و فقط اگر (هم مرتبه باشند) و جمع دو ماتریس اگر و آنگاه قرینه ماتریس اگر آنگاه قرینه را بصورت زیر تعریف میکنیم: ضرب اسکالر در ماتریس اگر و یک اسکالر باشد آنگاهدر ضرب اسکالر یک عدد در یک ماتریس ضرب میشود. در این نوع ضرب تمامی عناصر ماتریس در آن عدد ضرب می‌شوند به عنوان مثال: و نمایش ریاضی آن به صورت زیر می باشد: cA)ij = c(A)ij) ضرب ماتریسها اگر و آنگاه ضرب دو ماتریس را با علامت نمایش داده و بصورت زیر تعریف خواهیم کرد: در این نوع هر دو ضرب شونده و ضرب کننده از نوع ماتریس می‌باشند. بطور مشابه ضرب دو ماتریس نیز باید یک جنبه خوش تعریفی داشته باشد. ضرب دو ماتریس داده شده A و B زمانی خوش تعریف است که تعداد ستونهای ماتریس ضرب کننده با تعداد سطرهای ماتریس ضرب شونده برابر باشند. بر این ضرب دو ماتریس که شرایط قابل ضرب بودن را داشته باشند به صورت زیر بیان میشود: برای بدست آوردن عنصر روی سطر iام و ستون y ام ماتریس خاصل ضرب عناصر روی سطر iام ماتریس ضرب کننده و عناصر روی ستون j ام ماتریس ضرب شونده را در نظر گرفته و آنها در هم ضرب و جمع می کنیم. به صورت ریاضی حاصلضرب دو ماتریس بصورت زیر نمایش داده می شود: A × B)ij = (A)i1(B)1j + (A)i2(B)2j + ... + ...
ماتریس
کاربرد در شبیه سازی، پردازش تصویر، و ترافیک و سازه های شهری، حل معادلات طولانی ***************************************در تاریخ آمده است.که اولین بار بک ریاضیدان انگلیسی تبار بنام کیلی ماتریس را در ریاضیات وارد کرد.با توجه به آنکه در آن زمان ریاضیدانان اغلب به دنبال مسائل کاربردی بودند کسی توجهی به آن نکرد.اما بعدها ریاضیدانان دنباله ی کار را گرفتند تا به امروز رسید که بدون اغراق می توان گفت در هر علمی به گونه ای با ماتریس سروکار دارند.یکی از نقش های اصلی ماتریس ها آن است که آنها ابزار اصلی محاسبات عملی ریاضیات امروزی هستند.درست همان نقشی که سایقا اعداد بر عهده داشتند. از این نظر می توان گفت نقش امروز ماتریس ها همان نقش دیروز اعداد است.البته ماتریس ها به معنایی اعداد و بردارها را در بردارند..بنابراین می توان آنها را تعمیمی از اعداد و بردارها در نظر گرفت.در ریاضیات کاربردی ماتریس ها از ابزار روزمره هستند.زیرا ماتریسها با حل دستگاه معادلات خطی ارتباط تنگاتنگی دارند و برای حل ریاضی مسائل عملی مناسب ترین تکنیک فرمول بندی مسئله و یا تقریب زدن جوابهای مسئله با دستگاه معادلات خطی است که در نتیجه ماتریس ها وارد کار می شوند. از جنبه ی نظری فیزیک امروزی که فیزیک کوانتوم است بدون ماتریس ها نمی توانست بوجود آید.هایزنبرگ – اولین کسی که در فیزیک مفاهیم ماتریسها را به کار برد- اعلام کرد."تنها ابزار ریاضی من در مکانیک کوانتوم به آن احتیاج دارم ماتریس است".بسیاری از جیرهایی که تا به حال دیده اید مانند جبر اعداد مخنلط و جبر بردارها را با ماتریسها بسیار ساده می توان بیان کرد.*************************************ماتریسماتریس عبارت است از آرایشی (آرایه‌ای) مستطیل شکل از اعداد مختلط به طوری که عناصر این آرایه را درایه می‌نامیم و عنصر واقع در سطر ام و ستون ام را با نماد نشان می‌دهیم. ماتریسی که دارای سطر و ستون باشد را ماتریس از مرتبه در می‌نامیم.( )نکتههرگاه آنگاه ماتریس را مربع از مرتبه می‌نامیم. یک ماتریس را بصورت نمایش می‌دهیم.تاریخچهمطالعه روی انواع خاصی از ماتریسها مانند مربعهای جادویی و مربعهای لاتین ، به تاریخ قبل از میلاد نسبت داده شده است. معرفی و تکامل نمایش ماتریسها به عنوان شاخه‌ای از جبر خطی در نتیجه مطلعه روی ضرایب سیستم معادلات خطی و الگوها و روشهای حل آنها بوجود آمد. لایب نیتس به عنوان یکی از پایه گذاران علم حسابان در سال 1693، دترمینان ماتریسها را معرفی کرد. در ادامه کرامر روش خود را برای حل دستگاه معادلات خطی بر اساس دترمینان ماتریس ضرایب دستگاه معرفی کرد. این روش که به روش کرامر مرسوم است، بر ...