הוצאת שורש ריבועי

במתמטיקה, הוצאת שורש ריבועי היא הפעולה של חישוב שורש ריבועי של מספר או ערך נתון.

המקרה הפשוט ביותר הוא הוצאת שורש ריבועי ממספר שלם, כמו בדוגמה $\sqrt{17956}=134$. פעולה זו היא פשוטה יחסית; כל מחשבון כיס יכול לבצע אותה בקלות, ואפילו בעידנים הקדומים, לפני שמחשבים כאלה היו נפוצים, ניתן היה להשלים את המשימה על פיסת נייר, בדומה לחישוב מנה באמצעות חילוק ארוך.

באופן כללי יותר, הוצאת שורש ריבועי דורשת פתרון של משוואה מהצורה $x^2=a$, כאשר $a$ ידוע ו־$x$ נעלם. אופי החישוב תלוי במבנה האלגברי שבו מבצעים את הפעולה.

דוגמאות

הוצאת שורש ממספר ממשי או מרוכב

מציאת השורש של מספר ממשי נתון היא בעיה בסיסית באנליזה נומרית. כמו הרבה בעיות אחרות, הפתרון כולל שני מרכיבים: מציאת קירוב, ושיפורו ההדרגתי. את הקירוב הראשוני לשורש אפשר למצוא על ידי הוצאת שורש ממספר שלם. למשל, $\sqrt{0.65}=\frac{\sqrt{65}}{10}\approx \frac{\sqrt{64}}{10}=\frac{8}{10}=0.8$.

השלב הבא הוא הפעלת שיטת ניוטון-רפסון. אם $x_n$ הוא קירוב לשורש של a, אז $x_{n+1}=\frac{1}{2}(t+\frac{x_n}{t})$ הוא בדרך־כלל קירוב טוב יותר. כאשר הקירוב הראשון קרוב מספיק למטרה, שיטה זו מכפילה את מספר הספרות המדויקות בכל צעד.

בהצגה הקרטזית, השורש השני של מספר מרוכב $a+bi$ עבור $a,b\in \mathbb{ℝ}$ נתון על ידי הנוסחה $\sqrt{a+bi}=\pm (\frac{b}{2t}+ti)$, כאשר $t=\sqrt{\frac{\sqrt{a^2+b^2}-a}{2}}$. זוהי רדוקציה של הוצאת השורש ממספר מרוכב להוצאת שורש ממספר ממשי (חיובי).

הוצאת שורש ידנית ממספר עשרוני

כדי להוציא ידנית שורש ממספר עשרוני, מחלקים את המספר לזוגות (הנקודה העשרונית נמצאת בין הזוגות)
לדוגמה המספר 34927.8721 יחולק כך: $34927.8721$

נסמן את תוצאת הביניים ב־$X$. (בשלב הראשון X=0)

לוקחים את הזוג הגדול ביותר שעוד לא "טופל" ומצמידים אותו מימין לשארית מהסבב הקודם. (בשלב הראשון השארית היא 0) – נסמן את החיבור הזה ב-Y.
בכל שלב מחפשים את הספרה a הגדולה ביותר המקיימת: 20x+a)*a $\le$ Y)
רושמים את הספרה a מעל לזוג המתאים והשארית החדשה היא: Y - (20x+a)*a

דוגמה לחישוב:

$\begin{array}{c}186.89\\ \sqrt{34927.8721}\\ & & & & & x=0& 20x+a\equiv \underset{\_}{a}\\ \underset{\_}{}3& \underset{\_}{a}\times \underset{\_}{a}\le 3\\ \underset{\_}{1}& \underset{\_}{1}\times \underset{\_}{1}=1& \Rightarrow & a=1& \Rightarrow & x=\underset{\_}{1}& 20x+a\equiv 2\underset{\_}{a}\\ \underset{\_}{}249& 2\underset{\_}{a}\times \underset{\_}{a}\le 249\\ \underset{\_}{224}& 2\underset{\_}{8}\times \underset{\_}{8}=224& \Rightarrow & a=8& \Rightarrow & x=1\underset{\_}{8}& 20x+a\equiv 36\underset{\_}{a}\\ \underset{\_}{}2527& 36\underset{\_}{a}\times \underset{\_}{a}\le 2527\\ \underset{\_}{2196}& 36\underset{\_}{6}\times \underset{\_}{6}=2196& \Rightarrow & a=6& \Rightarrow & x=18\underset{\_}{6}& 20x+a\equiv 372\underset{\_}{a}\\ \underset{\_}{}331.87& 372\underset{\_}{a}\times \underset{\_}{a}\le 33187\\ \underset{\_}{298.24}& 372\underset{\_}{8}\times \underset{\_}{8}=29824& \Rightarrow & a=8& \Rightarrow & x=186\underset{\_}{8}& 20x+a\equiv 3736\underset{\_}{a}\\ \underset{\_}{}33.6321& 3736\underset{\_}{a}\times \underset{\_}{a}\le 336321\\ \underset{\_}{33.6321}& 3736\underset{\_}{9}\times \underset{\_}{9}=336321& \Rightarrow & a=9& \Rightarrow & x=1868\underset{\_}{9}\\ 0\\ \end{array}$

שיטת ניוטון-רפסון

שיטת ניוטון־רפסון היא שיטה איטרטיבית למציאת השורש של הפונקציה (בכחול), הנעשית באמצעות סדרת קירובים תוך שימוש במשיק (באדום)

שיטת ניוטון–רפסון היא אלגוריתם יעיל באנליזה נומרית, למציאת שורשים של פונקציה ממשית כלשהי, כלומר נקודות בהן הפונקציה מתאפסת.

בהנתן $a\in \mathbb{ℝ}$ כלשהוא, הסדרה הרקורסיוית

$\begin{array}{rl}{x}_{n+1}& =\frac{1}{2}(x_n+\frac{a}{x_n})\\ x_0& =a\end{array}$

מתכנסת אל השורש הריבועי של $a$. למשל:

$\begin{array}{rl}{x}_0& =100\\ x_1& =50.5\\ x_2& =26.2400990099\\ x_3& =15.02553012\\ x_4& =10.840434673\\ x_5& =10.032578511\\ x_6& =10.0000528956\\ ⋮& \end{array}$

הוצאת שורש מודולרית

מציאת השורש ריבועי של מספר נתון מודולו מספר אחר היא בעיה שכיחה בהצפנה מודרנית. לדוגמה במציאת השורש של 37 מודולו 63, הבעיה היא למצוא שלם $x$, המקיים $x^2\equiv 37(\mathrm{mod}63)$. הצעד הראשון לפתרון הבעיה הוא פירוקה לגורמים לפי משפט השאריות הסיני: $63=3^2\cdot 7$, ולכן עלינו למצוא מספר שיקיים בו זמנית את שתי המשוואות $x^2\equiv 37(\mathrm{mod}7)$ ו- $x^2\equiv 37(\mathrm{mod}{3}^2)$. למעשה, היכולת להוציא שורשים מודולו n שקולה, מבחינה חישובית, ליכולת לפרק את n לגורמים ראשוניים (ראו שיטת רבין).

אם $n=p^k$ הוא חזקה של מספר ראשוני, הוצאת שורש מודולו n קשה בערך כמו הוצאת שורש מודולו p עצמו. המעבר החישובי משורש מודולו p לשורש מודולו n נעשה באינדוקציה על k, כמו בלמה של הנזל. לא לכל מספר קיים שורש מודולו n; אם p איזוגי, אז שורש כזה קיים מודולו n אם ורק אם הוא קיים מודולו p - וכאשר יש למספר (שונה מאפס) שורש, יש לו בדיוק שניים. אם n הוא חזקת 2, אז קיים לו שורש אם ורק אם קיים שורש מודולו 8, ואם קיים שורש אז קיימים בדיוק ארבעה. (לפרטים בנושא זה, ראו חבורת אוילר).

הוצאת שורש ריבועי מודולו מספר ראשוני $p$ (אי-זוגי), מתחלקת לשני מצבים. אם $p\equiv 3(\mathrm{mod}4)$ אז $a^{\frac{p+1}{2}}=\pm a$, ולכן $a^{\frac{p+1}{4}}$ הוא שורש של $a$ או של $-a$ (רק לאחד מהם יש שורשים). המקרה השני, כאשר $p\equiv 1(\mathrm{mod}4)$, יותר מסובך.

הוצאת שורש בשדה סופי

נניח ש- $F={\mathbb{𝔽}}_q$ הוא השדה הסופי בן q אברים. החבורה הכפלית של השדה היא בת q-1 אברים. אם q הוא חזקת 2, לפי משפט לגראנז', $a^{q/2}$ הוא שורש של a. אם q איזוגי המצב דומה להוצאת שורש מודולו ראשוני (למרות שהוצאת שורש בשדה בגודל 27 היא משימה אחרת מהוצאת שורש מודולו 27).

הוצאת שורש בשדות מספרים

לפעמים רוצים לחשב את השורש של מספר שאיננו רציונלי, כגון $301+96\sqrt{5}$, באופן מדויק, ולקבל תשובה מאותה צורה (ולא רק מספר עשרוני, שהוא פתרון מקורב). זוהי בעיה קשה באופן כללי, אבל במקרים מסוימים אפשר לפתור אותה בקלות יחסית. הכלי המרכזי במקרה זה הוא הנורמה, שמוגדרת במקרה של השדה $\mathbb{\mathbb{Q}}[\sqrt{5}]$ לפי הנוסחה $N(a+b\sqrt{5})=a^2-5b^2$.

מכיוון ש- $N(301+96\sqrt{5})=301^2-5\cdot 96^2=44521=211^2$, ברור שהשורש $x+y\sqrt{5}$ (אם קיים שורש מצורה זו) יהיה בעל נורמה $211$ או $-211$, כלומר, $x^2-5y^2=\pm 211$ מצד שני, השורש מקיים $(x+y\sqrt{5}{)}^2=(x^2+5y^2)+2xy\sqrt{5}=301+96\sqrt{5}$, או $x^2+5y^2=301;2xy=96$. מחיבור וחיסור שתי המשוואות על $x^2,y^2$ מקבלים שהנורמה היא דווקא 211, $x=\sqrt{\frac{301+211}{2}}=\sqrt{256}=16$ והשורש הוא $\sqrt{301+96\sqrt{5}}=\pm (16+3\sqrt{5})$.

שורש ממטריצה חיובית או אופרטור

לא לכל מטריצה קיים שורש מעל שדה המספרים הממשיים: יש מטריצות A עבורן לא ייתכן ש- $X^2=A$. לעומת זאת, אם A היא מטריצה חיובית, אפשר למצוא את השורש (הריבועי, ומכל סדר) על ידי לכסון אורתוגונלי והוצאת השורש מן המטריצה האלכסונית המתקבלת.

ראו גם

• ארבע פעולות החשבון
• פירוק מספר שלם לגורמים

קישורים חיצוניים

• גדי אלכסנדרוביץ', אז איך באמת מוצאים שורש ריבועי?, באתר "לא מדויק",