פולינום ממשי מדרגה קטנה מ-n הוא ביטוי מהצורה p(x)=a0+a1x+a2x2+⋯+an−1xn−1. משפט ידוע באלגברה קובע שפולינום כזה נקבע ביחידות לפי ערכיו ב-n מקורות שונים. למשל, כל קו ישר (פולינום מדרגה קטנה מ-2) נקבע ביחידות על ידי שתי נקודות שדרכן הוא עובר. באופן כללי, בהינתן n נקודות (x1,y1),…,(xn,yn) שעבורן xi=xj לכל i=j, קיים פולינום אחד ויחיד p(x) מדרגה קטנה מ-n המקיים p(x1)=y1,…,p(xn)=yn; פולינום זה נקרא פולינום האינטרפולציה של הנקודות.
בבעיית האינטרפולציה נתונות הנקודות (x1,y1),…,(xn,yn) המקיימות xi=xj, וברצוננו לחשב את המקדמים a0,…,an−1 של פולינום האינטרפולציה.
(א) (26 נק') לכל i≤j נסמן ב-pi,j את פולינום האינטרפולציה של הנקודות (xi,yi),…,(xj,yj). רשמו שלושה פולינומים פשוטים q(x),r(x),s(x) מדרגה 0 או 1, שעבורם מתקיים
(∗)pi,j+1(x)=s(x)q(x)⋅pi,j(x)−r(x)⋅pi+1,j+1(x)
(ב) (7 נק') הציגו אלגוריתם תכנון-דינמי לבעיית האינטרפולציה, המבוסס על נוסחת הנסיגה מסעיף (א). לשם פשטות, החשיבו פעולות אריתמטיות על מספרים כפעולות אלמנטריות.