Résolution d'une équation par balayage

On cherche dans cet exercice à déterminer des valeurs approchées de solution d'équation par balayage. Cette démarche ne fournit pas nécessairement la valeur exacte mais elle est simple à mettre en œuvre.

On considère une fonction \(f\) vérifiant les propriétés suivantes :

  • \(f\) est définie sur un intervalle \(\left[a~;~b\right]\) ;
  • \(f\) est strictement monotone1 sur \(\left[a~;~b\right]\) ;
  • \(f(a)\) et \(f(b)\) sont de signes contraires ;
  • \(f\) est continue2 sur \(\left[a~;~b\right]\).

Ces propriétés garantissent que la fonction \(f\) s'annule une unique fois sur \(\left[a~;~b\right]\). On cherche donc à résoudre l'équation \(f(x)=0\). On appelle \(\alpha\) l'unique solution de cette équation.

Résolution par balayage

Afin de déterminer un encadrement de largeur \(h\) de \(\alpha\), on procède comme suit :

  • on considère une variable \(x\) initialement égale à \(a\) ;
  • tant que \(f(x + h)\) est du signe de \(f(a)\), on ajoute \(h\) à \(x\). On balaie donc l'intervalle de \(h\) en \(h\) ;
  • dès que \(f(x + h)\) change de signe, on renvoie le couple \((x~;~x+h)\) : c'est notre encadrement.

On présente ci-dessous deux versions de l'exercice : l'une pour déterminer un encadrement de \(\sqrt2\), l'autre plus générale.

assert ?

Le mot clé assert est utilisé en Python afin de vérifier que des propositions sont vraies.

Ainsi, l'instruction assert 3 + 5*7 == 38 permet de vérifier que l'expression 3 + 5*7 est bien évaluée à 38.

Si c'est le cas, le programme continue de se dérouler normalement. Dans le cas contraire, le programme est interrompu et une erreur est signalée.

Encadrement de \(\sqrt2\)

La fonction considérée est \(f:x\mapsto x^2-2\).

On sait que \(f(1)=1^2-2=-1<0\) et \(f(2)=2^2-2=2>0\). De plus cette fonction est continue sur \(\left[1~;~2\right]\).

L'équation \(f(x)=0\) admet donc une unique solution sur \(\left[1~;~2\right]\). Cette solution est \(\sqrt2\).

Comme \(f(1)\) est strictement négatif, on balaie l'intervalle jusqu'à ce que \(f(x+h)\) soit strictement positif.

Compléter la fonction balayage qui prend en paramètres deux nombres a et h et renvoie un encadrement de \(\sqrt2\) de largeur h.

Comme son nom l'indique, la variable racine_de_2 contient une valeur approchée de \(\sqrt2\).

Les tests de cet exercice vérifient que racine_de_2 est bien comprise entre les deux valeurs renvoyées et que la largeur entre celles-ci est bien « égale1 » à h.

Exemples
>>> balayage(1, 0.1)
(1.4000000000000004, 1.5000000000000004)
>>> balayage(1.4, 0.01)
(1.41, 1.42)
>>> balayage(1.41, 0.001)
(1.4139999999999995, 1.4149999999999994)

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.1280132mhS)cleP=3tfnp:avgby;s5or 1(kx+*4iwud,/050M0i0m0r0J0h0x0B0g0h0r0x0x0k010m0J0p010406050x0L0c0c0r0A0v040e0z0h0L0)0z0o050O0:0=0@0_0.0p040519121c0O190.0M0J0s0X0Z0#0%0d0J0t0d0h1q0d0m0,050S0u0h0i1l0!0$011p1r1t1r0m1z1B1x0m0A1a0m0d0X0|0x0p0r0o0%0b011D1n010n0U0i0o0r0c0i1x1W1Y1%1F1*1B1-1/0,0a0B0j0A0z0p0z0x0J0 0o0B0Q1U0A0A0i0g27121=0o1a0O1S2k1P1R1Q1y0M1@0%1t0o1,241x1i1k0Y1E2u0J2w0o0z2A1x0p2d1a2i2k2O0/1X282C1(2H0A0?0h0,0C2h2S0-2R1?2U1F2W2Y0,0b2$1Y2(2i2t012-0r2Z040l2;2j0.2@2+0%2`2|0I2 2?2S2^350,0y381d2M122A2n0M1R2s33010g2I1:1a3j1b3h2Q132%053q0Q2N3a3o0E0,0Q0n3f321m1F0K0,0B3K3E3M340n0,0u2{0r0v0r0t0i3R2*3T010+040D3(2T3*0o0,0r3/2^3,0N383Q3L2D2_0,0d3^3o3,0f0q38060B4a3}3S3 3=040F3|2)3:3 0z0,0k4i3~2V3?484b4c3)3 3G040K1p1B4p4d1(3,3.3y2=4j3b0,4h4I2j4v4k1(4m040G4D4w4r04424O3D4X1F454W4R1F4T0H0H4*2^0c0J2/4:3o4T020h0m0w4o4#4Q4;4?042:4#4K440,474#494u4b573;4M4^3*4T4 2O513o4f4N5m5f4l0,4V505s4Y4!2O5c4a5x1F4y2d0m0L0A115w4q4(0,4H2Q5M345h565R3+0,3{5L4E2,5T5r5V4T5v5%5!5S4Z433*4)5b123B0i2k2L5^3i1j3k2n2q2l0r1A5{0O3j0.650R0T0V04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.1280132mhS)cleP=3tfnp:avgby;s5or 1(kx+*4iwud,/050M0i0m0r0J0h0x0B0g0h0r0x0x0k010m0J0p010406050x0L0c0c0r0A0v040e0z0h0L0)0z0o050O0:0=0@0_0.0p040519121c0O190.0M0J0s0X0Z0#0%0d0J0t0d0h1q0d0m0,050S0u0h0i1l0!0$011p1r1t1r0m1z1B1x0m0A1a0m0d0X0|0x0p0r0o0%0b011D1n010n0U0i0o0r0c0i1x1W1Y1%1F1*1B1-1/0,0a0B0j0A0z0p0z0x0J0 0o0B0Q1U0A0A0i0g27121=0o1a0O1S2k1P1R1Q1y0M1@0%1t0o1,241x1i1k0Y1E2u0J2w0o0z2A1x0p2d1a2i2k2O0/1X282C1(2H0A0?0h0,0C2h2S0-2R1?2U1F2W2Y0,0b2$1Y2(2i2t012-0r2Z040l2;2j0.2@2+0%2`2|0I2 2?2S2^350,0y381d2M122A2n0M1R2s33010g2I1:1a3j1b3h2Q132%053q0Q2N3a3o0E0,0Q0n3f321m1F0K0,0B3K3E3M340n0,0u2{0r0v0r0t0i3R2*3T010+040D3(2T3*0o0,0r3/2^3,0N383Q3L2D2_0,0d3^3o3,0f0q38060B4a3}3S3 3=040F3|2)3:3 0z0,0k4i3~2V3?484b4c3)3 3G040K1p1B4p4d1(3,3.3y2=4j3b0,4h4I2j4v4k1(4m040G4D4w4r04424O3D4X1F454W4R1F4T0H0H4*2^0c0J2/4:3o4T020h0m0w4o4#4Q4;4?042:4#4K440,474#494u4b573;4M4^3*4T4 2O513o4f4N5m5f4l0,4V505s4Y4!2O5c4a5x1F4y2d0m0L0A115w4q4(0,4H2Q5M345h565R3+0,3{5L4E2,5T5r5V4T5v5%5!5S4Z433*4)5b123B0i2k2L5^3i1j3k2n2q2l0r1A5{0O3j0.650R0T0V04.
Cas général

On considère désormais une fonction \(f\) quelconque qui sera passée en paramètre de la fonction balayage.

On sait que \(f(a)\) et \(f(b)\) sont de signes contraires mais on ignore si \(f(a)\) est positif ou négatif... Or la méthode par balayage nécessite de savoir si \(f(x+h)\) et \(f(a)\) ont le même signe ou non !

Cette condition peut être testée astucieusement : \(f(x + h)\) est du signe de \(f(a)\) si leur produit \(f(x + h) \times f(a)\) est positif ou nul (en effet, le produit de deux nombres de mêmes signes est positif).

Compléter la fonction balayage qui prend en paramètres la fonction \(f\) étudiée et deux nombres a et h et renvoie un encadrement de la solution de \(f(x)=0\) de largeur h.

Les tests de cet exercice vérifient que la solution attendue est bien comprise entre les deux valeurs renvoyées et que la largeur entre celles-ci est bien « égale » à h.

Exemples

La fonction f renvoie x*x -3. La valeur cherchée dans cet exemple est donc \(\sqrt3\).

Attention, les tests proposent d'autres fonctions f.

>>> balayage(f, 0, 1)
(1, 2)
>>> balayage(f, 1, 0.1)
(1.7000000000000006, 1.8000000000000007)
>>> balayage(f, 1.7, 0.01)
(1.73, 1.74)

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.1280132mhS)cle-P=3tfn,p:avgby;s560or 1(k8+*4iwu7d9x/050R0i0n0t0N0h0z0F0g0h0t0z0z0l010n0N0r010406050z0P0c0c0t0E0x040e0D0h0P0/0D0p050U0_0{0}0 0@0r04051f181i0U1f0@0R0N0u0%0)0+0-0d0N0v0d0h1w0d0n0=050Y0w0h0i1r0*0,011v1x1z1x0n1F1H1D0n0E1g0n0d0%120z0r0t0p0-0b011J1t010o0!0i0p0t0c0i1D1$1(1-1L1:1H1?1^0=0a0F0k0E0D0r0D0z0N150p0F0W1!0E0E0i0g2d181{0p1g0U1Y2q1V1X1W1E0R1}0-1z0p1=2a1D1o1q0(1K2A0N2C0p0D2G1D0r2j1g2o2q2U0^1%2e2I1.2N0E0|0h0=0G2n2Y0?2X1|2!1L2$2(0=0b2,1(2.2o2z012?0t2)040m2`2p0@2}2;0-30320M352|2Y2~3b0=0A3e373g392 0D2%310=0B3l2/2Z1s2=3q2@040Q3v383y3a3A3s040J3E3n3G3p3r320S3e1j2S182G2t0R1X2y3o0g2O1_1g3X1h3V2W192-053%0W2T3N2J010I0=0W0o3T3F3_0O0=0F3 3^2#0o0=3~3/2{3w2~0;040H452:3O0p0=0T4i3x3_4f0f0s3l0F4v44401.3{042j0n0P0E174b2p4x462=4m3e4J4j3_0D0=0L4N4d3o4l044n4H044O4p1.4R040j4U4y1L0c0N0=344!064@4V3O4A3}4o2~424#4}4W48040w310t0x0t0v0i513O4f4h4!4_3_4X4a2W4-0-4f0q4,4K3a0=0t5c4q0=5p4!4$3h0=0d5v1.4r4t4?4w5A4W4M5z5h4(0=0l5q4P2#5t4u4w5O1L4A0O1v1H5S4%4L045k3:5m015e5E5*5u5g5.4r5(2~4)4T5N5.5j5;5n0=5f5l5r2 5M2U5K3O4)0K5`5L045D5@665_5~664)020v0n0y5R6l5T4.4:040C615/0=5H2U065J5J5Y5s4Y6e6b5Q6K5i682-6a4Q0=6d6t5)6I6h6D6G5.4A4C4E4G696H6A4g6z4X4Z656u62045y6*5 6P2{6R5P046U6_664X6Y5-6j0=0f3v0U3=0i2q2R7c3W1p3Y2t2w2r0t1G7f0U3X0@7p0X0Z0#04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.1280132mhS)cle-P=3tfn,p:avgby;s560or 1(k8+*4iwu7d9x/050R0i0n0t0N0h0z0F0g0h0t0z0z0l010n0N0r010406050z0P0c0c0t0E0x040e0D0h0P0/0D0p050U0_0{0}0 0@0r04051f181i0U1f0@0R0N0u0%0)0+0-0d0N0v0d0h1w0d0n0=050Y0w0h0i1r0*0,011v1x1z1x0n1F1H1D0n0E1g0n0d0%120z0r0t0p0-0b011J1t010o0!0i0p0t0c0i1D1$1(1-1L1:1H1?1^0=0a0F0k0E0D0r0D0z0N150p0F0W1!0E0E0i0g2d181{0p1g0U1Y2q1V1X1W1E0R1}0-1z0p1=2a1D1o1q0(1K2A0N2C0p0D2G1D0r2j1g2o2q2U0^1%2e2I1.2N0E0|0h0=0G2n2Y0?2X1|2!1L2$2(0=0b2,1(2.2o2z012?0t2)040m2`2p0@2}2;0-30320M352|2Y2~3b0=0A3e373g392 0D2%310=0B3l2/2Z1s2=3q2@040Q3v383y3a3A3s040J3E3n3G3p3r320S3e1j2S182G2t0R1X2y3o0g2O1_1g3X1h3V2W192-053%0W2T3N2J010I0=0W0o3T3F3_0O0=0F3 3^2#0o0=3~3/2{3w2~0;040H452:3O0p0=0T4i3x3_4f0f0s3l0F4v44401.3{042j0n0P0E174b2p4x462=4m3e4J4j3_0D0=0L4N4d3o4l044n4H044O4p1.4R040j4U4y1L0c0N0=344!064@4V3O4A3}4o2~424#4}4W48040w310t0x0t0v0i513O4f4h4!4_3_4X4a2W4-0-4f0q4,4K3a0=0t5c4q0=5p4!4$3h0=0d5v1.4r4t4?4w5A4W4M5z5h4(0=0l5q4P2#5t4u4w5O1L4A0O1v1H5S4%4L045k3:5m015e5E5*5u5g5.4r5(2~4)4T5N5.5j5;5n0=5f5l5r2 5M2U5K3O4)0K5`5L045D5@665_5~664)020v0n0y5R6l5T4.4:040C615/0=5H2U065J5J5Y5s4Y6e6b5Q6K5i682-6a4Q0=6d6t5)6I6h6D6G5.4A4C4E4G696H6A4g6z4X4Z656u62045y6*5 6P2{6R5P046U6_664X6Y5-6j0=0f3v0U3=0i2q2R7c3W1p3Y2t2w2r0t1G7f0U3X0@7p0X0Z0#04.

  1. on ne teste pas l'égalité stricte de l'écart en raison de possibles erreurs d'arrondis. 

  2. la continuité est une propriété mathématique qui assure que le graphe de \(f\) peut être tracé sans lever le crayon.